I recently upgraded the debian version from 8 to 9 and my surprise was to not being able to connect to the newly upgraded server with my usual ssh key.
It turns out that beyond OpenSSH version 6.6, the "unsafe algorithms" have been removed, including my kinda old dss key.

All you have to do is to create a new one. I choose ecdsa: $ ssh-keygen -t ecdsa
Do not forget to put the newly pub key (e.g. the content of ~/.ssh/id_ecdsa.pub) in ~/.ssh/authorized_keys of the upgraded server.

Well, that was kinda short. Enjoy! :)