Tente regenerar as chaves do host:
sudo rm /etc/ssh/ssh_host_* && sudo dpkg-reconfigure openssh-server
Você pode obter mais informações de depuração do ssh com a opção -v, bem como procurar no log do servidor ssh, para o debian / ubuntu, isso é /var/log/auth.log