You are getting this because something has changed (like new NIC, new IP, change on server software, etc). Security focusFocus has a nice article on SSH host key protection.:
Why can a host key change? The machine to which you wish to connect has been moved to a different DNS name or IP address, or it's been replaced by a new one entirely.
Just remove the key (using SFTP or similar) from the server, by editing the $HOME/.ssh/known_hosts file, and accept the new one upon next connection.
Your connection might be getting dropped because of the StrictHostKeyCheckingStrictHostKeyChecking setting. See this thread for a similar issue.