This prompt can come up for a variety of reasons. For me, occasionally I can’t login via sFTP to a website using Transmit. I get the prompt:
Host Key Changed for yourdomain.com
The server’s host key has changed since your last connection. This is most likely due to a server change, but you should check with your server administrator to be sure. Click OK to accept the new host key.
In some scenarios clicking OK will fix it. When it doesn’t waddya do?
After fumbling around with it for longer than I liked to admit the solution ended up being pretty simple. It was jut hiding in the terminal window.
1. Take a deep breath.
2. Open up the terminal window
3. paste this in it: rm .ssh/known_hosts
4. Hit return.
That should do it. Try to connect again and you should be all set.
I’m allergic to Windows. Feel free to comment the solution for Windows.