Это может дать вам более подробную информацию о причине. если на сервере отсутствуют ключи rsa и dsa, исправьте их:
ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_rsa_key
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key
У меня была эта точная проблема. Выключенный разъем питания для HD выскользнул из гнезда. Вставьте его обратно и загрузите машину. Решение было замаскировано наличием нескольких дисков SATA в корпусе ПК - не помню имя диска, с которого я обычно загружался.