回答くれた方、付き合ってもらってありがとうございます。

>>623
DSAでは作ったことないです。

>>624
そう思って、rm -rf ~/.ssh してみたんですが、かわらなかったです。

また、ダメもとで以下をやってみたんですが、
rm -rf ~/.ssh
sudo aptitude purge openssh-server openssh-client
#/etc/ssh がないのを確認
sudo aptitude reinstall openssl
sudo aptitude install openssh-server

ssh-vulnkeyで以下のファイルがCOMPROMIZED言われてしまいます。
/etc/ssh/ssh_host_{rsa,dsa}_key.pub

かなりお手上げ状態…。testingにしてみたら変わるでしょうか。