How to generate a public/private key (UNIX)

ssh-kegen(1)

You need the host key so you know you are connecting to the right server and not a fake one.

# private key
openssl genrsa -out privkey.pem 2048

# public key
openssl rsa -in privkey.pem -pubout -out pubkey.pem

For more information:
http://www.openssl.org/docs/apps/rsa.html
http://www.openssl.org/docs/HOWTO/keys.txt

It differs from one distribution to another. On Ubuntu use this command:

ssh-keygen

It will generate two keys, one public (the one you will share to the server) and the other is private and you shall not share with anyone. Once the public key is copied in the ~/.ssh/authorized_keys in the server, you can login without being prompt for password.