SSH suddenly asking for password

Try adding -o 'PubkeyAcceptedKeyTypes +ssh-rsa' to the client ssh connection command. I have no idea why, but this allowed me to connect again in a situation similar to yours (probably some misconfigured apt install command on the server on my part). Phew.

As aecolley pointed out on superuser, the answer was staring me in the face. The problem was with permissions, and the reason was that the user with uid 501 owned my home directory. Why, you ask? Because I'd (kind of accidentally) used rsync to copy a bunch of files there from my laptop, and rsync appears to have used my laptop's user id (501, the default on OS X) for the job.

chown root . from my home directory on the server fixed the problem.