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.
ssh -Q. This is asking how to trouble-shoot a failure of SSH. I did find some of the material at superuser.com/q/962918/93541 and elsewhere helpful in identifying this solution, but the answer there describes how to use
ssh -Qand does not answer this question (e.g., it doesn't explain how to fix this problem), so in my view it's not a dup. The one on Unix & Linux is very similar; I wish I'd seen that one earlier. Thanks again for the links!