When you log in to a server for the first time, you will be provided with that server's key fingerprint, which you should immediately verify (that there's no man-in-the-middle compromise).
server gives its fingerprint
you confirm that the host key really produces that fingerprint
Here's how to create a new key pair on OS X.