http://elinux.org/RPi_Remote_Access
Initial Setup
sudo rm /etc/ssh/ssh_host_* && sudo dpkg-reconfigure openssh-server
Prior to your initial remote access it is recommended that you generate unique host public/private keys with the following command
You can execute these commands after having logged in remotely, and if executed while logged in from a remote client you will not be disconnected mid-session. However, after you generate unique you will need to clean up your client’s known_hosts.
This extra command (and subsequent follow up to update the cached public key on all clients who’ve already remotely connected to your Raspberry Pi) may seem like a hassle, but without doing this you leave yourself wide open to a man-in-the-middle attack because your “private” host ID keys are widely available to anyone who has downloaded the same SD card image as you.