If you can't connect to a SSH server, then you may need to rebuild your keys.
To do so, run the following...
rm -r /etc/ssh/ssh*key
cd /etc/ssh
ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key
ssh-keygen -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key
service sshd restart