This article is just a tip, but useful. Did you notice that with new debian an old working ssh key is no more able to make you connect to the server by default? This is valid if you had an old rsa key and tried to connect in SSH with keys authentication. Why? because the new openssh version (7.0+) deprecated DSA keys and is not using DSA keys by default (not on server or client). The keys are not preferred to be used anymore, so if you can, I would recommend to use RSA keys where possible.
If you really need to use DSA keys, you need to explicitly allow them in your client config using
PubkeyAcceptedKeyTypes +ssh-dss
Put that line in /etc/ssh/sshd_config and restart openssh server, and all would be ok now
I think this would have saved you a lot of time.