What happens is, during the initial connection between client and server, they exchange public keys.
Public keys are the public component of a key pair.
Key pairs work in such a way that you can encrypt using one key, and decrypt using the other and it is very difficult to try to get the other key if you only have one. So the client encrypts a random string using the server's public hostkey, and sends it to the server. The client decrypts using it's private key, and checks it with the original random string it has saved during the exchange. To prevent this, you need to download the Ssh2 hostkey for the server you are going to connect to and make it available to your ssh client. Doesn't hurt to just do both for good measure.