SSH suddenly asking for password

Question

General problem

I have my computer (Mac OSX 10.9.4) and a remote server (Ubuntu 14.04.1 LTS). I used ssh-keygen to create an ssh key (with no passphrase), added the public key to the server's .ssh/authorized_keys, and all was good in the world. Then, earlier today, ssh started asking me for a password again.

What might have caused it

I'm really not sure what caused this - these are my best guesses:

• I did have to remove some files from my home directory on the remote server when I accidentally copied a git repository there (I didn't commit or anything from there, just copied things over and then rm'd them). From what I can tell from my command history, there aren't ssh-relevant files that I removed, just .git, .gitignore, and various *.sw? files leftover from vim.
• I ran ssh-keygen -l -f ~/.ssh/authorized_keys on the remote server to see the fingerprints of (I think) the keys in that file.

Relevant logs

When I run ssh -v -i ~/.ssh/mykey_rsa user@serverip, I get this:

OpenSSH_6.2p2, OSSLShim 0.9.8r 8 Dec 2011
debug1: Reading configuration data /Users/myusername/.ssh/config
debug1: Reading configuration data /etc/ssh_config
debug1: /etc/ssh_config line 50: Applying options for *
debug1: Connecting to {ip address} [{ip address}] port 22.
debug1: Connection established.
debug1: identity file .ssh/mykey_rsa type 1
debug1: identity file .ssh/mykey_rsa-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.2
debug1: Remote protocol version 2.0, remote software version
OpenSSH_6.6.1p1 Ubuntu-2ubuntu2
debug1: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 pat OpenSSH*
debug1:  Miscellaneous failure (see text)
No credentials cache file found

debug1:  An invalid name was supplied
unknown mech-code 0 for mech 1 2 752 43 14 2

debug1:  Miscellaneous failure (see text)
unknown mech-code 0 for mech 1 3 6 1 5 5 14

debug1:  Miscellaneous failure (see text)
unknown mech-code 2 for mech 1 3 6 1 4 1 311 2 2 10

debug1:  An unsupported mechanism was requested
unknown mech-code 0 for mech 1 3 5 1 5 2 7

debug1:  Miscellaneous failure (see text)
unknown mech-code 0 for mech 1 3 6 1 5 2 5

debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr [email protected] none
debug1: kex: client->server aes128-ctr [email protected] none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Server host key: RSA {fingerprint}
debug1: Host '{ip address}' is known and matches the RSA host key.
debug1: Found key in /Users/myusername/.ssh/known_hosts:16
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: .ssh/otherkey_rsa
debug1: Authentications that can continue: publickey,password
debug1: Offering RSA public key: .ssh/mykey_rsa
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: password
user@serverip's password: 

I find it kind of strange that it tried a different ssh key (otherkey_rsa) before the one I told it to use (mykey_rsa), but I don't know enough about ssh to parse this well.

Meanwhile, the remote server's /var/log/auth.log helpfully says

Aug 12 02:04:19 servername sshd[22147]: error: Could not load host key: /etc/ssh/ssh_host_ed25519_key
Aug 12 02:04:19 servername sshd[22147]: Authentication refused: bad ownership or modes for directory /root

Permissions

Local/on my computer:

~/                     drwxr-xr-x+ 105 myusername staff 3570 Aug 11 23:14
~/.ssh/                drwx------   13 myusername staff  442 Aug 11 23:14
~/.ssh/mykey_rsa.pub   -rw-r--r--    1 myusername staff  397 Aug  5 20:52
~/.ssh/mykey_rsa       -rw-------    1 myusername staff 1675 Aug  5 20:52

Remotely/on the server:

~/                     drwxr-xr-x    8        501 staff 4096 Aug 12 02:16
~/.ssh/                drwx------    2 remoteuser root  4096 Aug 12 01:49
~/.ssh/authorized_keys -rw-------    1 remoteuser root   794 Aug 12 01:44

Answer 1

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.