So here's is my guide to change the already generated ssh keys that everyone has installed on kali:
After all we are hot on security right???? We dont want the same keys as the next man do we (MITM)..
Move the default Kali ssh keys to a new folder:
cd /etc/ssh/
mkdir default_kali_keys
mv ssh_host_* default_kali_keys/
This will move your default keys to the new folder.
Regenerate the keys:

dpkg-reconfigure openssh-server
Creating SSH2 RSA key; this may take some time .
Creating SSH2 DSA key; this may take some time .
Creating SSH2 ECDSA key; this may take some time .
insserv: warning: current start runlevel(s) (empty) of script `ssh' overrides LSB defaults (2 3 4 5).
insserv: warning: current stop runlevel(s) (2 3 4 5) of script `ssh' overrides LSB defaults (empty).
Verify ssh key hashes are different:
md5sum ssh_host_*
Compare new key hashes to the hashes below)
cd default_kali_keys/
md5sum *
b9419ea3a8fff086c258740e89ca86b8 ssh_host_dsa_key
f9a5b57d7004e3740d07c5b037d15730 ssh_host_dsa_key.pub
58e49e0d7b24249c38db0c9cf595751b ssh_host_ecdsa_key
597c83fabf3c1e4f2c7af74af05ac671 ssh_host_ecdsa_key.pub
cc0d92036bb86797bed354338faa7223 ssh_host_rsa_key
cc9ddc90b891b5251ed4ea8341495e84 ssh_host_rsa_key.pub
Job done !!!! I would also change the default port from 22 to another in the ssh_config
Here is my win 7 phone running ssh connected to Kali and running attaxsuite:
http://s1302.photobucket.com/user/pe.22fff.jpg.html
http://s1302.photobucket.com/user/pe.02639.jpg.html
http://s1302.photobucket.com/user/pe.26aa9.jpg.html
Kali screens:
http://s1302.photobucket.com/user/pe.bef0f.jpg.html
Kind Regards Dee