あとは /etc/ssh/ssh_host_*のパーミッションがおかしくなっていないの
の確認。
/etc/ssh_host_*.pubは644、/etc/ssh_host_*_keyは600