It doesn't really matter which system you make the keys on just be sure your secret key doesn't get out. The public key is used to encrypt messages and the private key is used to decrypt those messages. The server authenticates you by encrypting a random character with your public key then you decrypt it with your private key and confirm with the server that the character you received is the one it sent.
Originally Posted by roundhay
The passphrase is used to encrypt the secret key that way even if it gets stolen hopefully it can't be used. The secret key is decrypted on the local machine so if you are having errors with that then maybe you are having some kind of key board issue like a numlock being on or a caps lock (I just had this problem the other day with someone trying to SSH).
Basically, the public key goes to the server and needs to be added to the authorized_keys file. Once the public key is copied to the server you want to
Check this out if you are still lost it helped me. http://www.ibm.com/developerworks/library/l-keyc.html
cat id_dsa.pub >> ~/.ssh/authorized_keys