SSH が繋がらないというので調べてみたら sshd が以下のようなログを吐いていました。
僕は普段は RSA か ECDSA しか使っていないので気づいていませんでしたが、OpenSSH 7.0 以降は DSA 鍵*1がデフォルトで利用できないようになっていました。確か SSH の DSA は鍵長が 1024bit 固定だったはずで、それ以外の長さだと互換性に問題が出たりと問題児だったので、結局サポートが切られたというこことでしょうかね。元々 RSA を置き換えるために入ったのが DSA だったはずですが、RSA よりも先に退役してしまうとは思いませんでした。
OpenSSH 7.0 was released on 2015-08-11
* Support for ssh-dss, ssh-dss-cert-* host and user keys is disabled by default at run-time. These may be re-enabled using the instructions athttp://www.openssh.com/legacy.html