Since I’ve upgraded to Ubuntu 16.04, SSH also was upgraded. In the version shipped with Ubuntu, ssh-dsa keys are deprecated. This means that if you perform a reinstall and transfer your old files (and old .ssh directory), you may actually have keys that the server will accept, but your local client won’t.
*sigh*.
Generate some new keys. Use rsa for a well-supported / broadly-accepted key format, use ecdsa or ec… for the shiny new thing where current consensus thinks it’s pretty secure.