This is a result of upgrading to OpenSSH 7.0. As the release notes for OpenSSH 7.0 say, "Support for ssh-dss host and user keys is disabled by default at run-time".
The solution is to add the following line to
~/.ssh/config on every client machine (every machine where you run the SSH client):
If the server is using OpenSSH 7.0 or newer, you'll also need to add this line to
/etc/ssh/sshd_config on each server machine.
Alternatively, you can generate an entirely new SSH key and add it to your authorized_keys file on every server you ever want to log into. I recommend you use RSA, to avoid compatibility woes. I don't recommend ECDSA, as apparently gnome-keyring-daemon doesn't automatically pick up SSH keys of type ECDSA.
Editorial remark: Why did the OpenSSH folks disable DSA keys? I don't know. As far as I'm able to ascertain, there's nothing wrong with the security of DSA keys (ssh-dss). The OpenSSH web page claims that ssh-dss is weak, but as far as I'm aware, 1024-bit ssh-dss is no weaker than 1024-bit RSA, and 1024-bit RSA keys are not disabled.