I wasn't making any Mac vs. Windows vs. anything else comments. Only that this same error will come up when the host key in your local directory for your user doesn't match the host key stored the last time you went to that machine.
Usually it happens when the machine is reloaded, or moved to a new virtual, or... anything that makes SSH on the other side have a new private key.
The "fix" is easy - go into the local cache file and remove the entry line for that machine. It's cut off in the example above, but it tells you the file/location of your local cache file. vi <filename> ... down to the line for that machine, dd, :wq!, done.
Standard UNIX OpenSSH admin stuff here. Nothing Mac about it, other than Mac's run on a flavor of BSD, kinda...
For a longer-term solution -- when setting up a new Unix system, create SSH keypair during the install, copy the public key to your local machine, use keypair access only, and turn off password login support.
That'd be "normal" keypair use in a production Unix environment.
But that's a bit "hardcore" for the average non-production system SSH user.
No "Mac attitude" from me here on this one. This is just basic OpenSSH usage stuff. The wording of the error itself comes from the OpenSSH folks, not Apple, not HP (HP-UX), not IBM (AIX), not Oracle/Sun (Solaris), etc etc etc... it's the same error on all platforms that rely on OpenSSH upstream unless the vendor decided to repackage OpenSSH and change all the error messages, and that'd be crazy, since all the books, websites, and other references would have this error message in them... since OpenSSH began.
I first saw this error message sometime around 1991 or so, I suppose. Long ago enough that I don't remember. Don't think I needed the O'Reilly book on OpenSSH to figure this one out.... needed the book back then to figure out how to build keystores for multiple admins using key-based logins without passwords though.
Some tools have come along since then that make that part a little easier... but it's still pretty hokey. Most of the other methods of user authentication are worse than just managing your key cache...