So we all know of debian’s SSL woes.

Here is the command that I used on boxes to fix it.

rm /etc/ssh/ssh_host_*
apt-get install openssl openssh-server
dpkg-reconfigure openssh-server