Server authentication is done during Diffie-Hellman key exchange through a single public-key operation. When public-key authentication is used to authenticate the server, the first connection is very important. During the first connection the client will display a message similar to the one in Figure First connection to a remote host.
At this point, you should verify the validity of the fingerprint, for example by contacting the administrator of the remote host computer (preferably by telephone) and asking the administrator to verify that the key fingerprint is correct. If the fingerprint is not verified, it is possible that the server you are connecting to is not the intended one (this is known as a man-in-the-middle attack).
After verifying the fingerprint, it is safe to continue connecting. The server public key will then be stored on the client machine. The location depends on the client implementation (on Unix it is the ~/.ssh2/hostkeys directory).
After the first connection, the local copy of the server public key will be used in server authentication.