On your local machine cd into the .ssh directory in your home "~/" directory. If it doesn't exist you can create it with "mkdir ~/.ssh". Next generate your public/private keys and copy the public key to the remote server.

cd ~/.ssh
ssh-keygen -t rsa -b 4096
# will take a couple seconds but when finished
# specify a full path (if there is already an existing key) or hit enter to install to the default location ~/.ssh
# when it prompts for a passphrase just hit enter
# and enter again when it asks to confirm the passphrase
# then we copy the public key the remote server (this assumes you don't already have an authorized_keys file)
# copy and paste the contents of the id_rsa.pub file into the authorized_keys file otherwise
scp id_rsa.pub user@yourdomain.com:.ssh/authorized_keys

You'll need to edit your ssh config file and restart the process to allow for public/private key authentication.

vim /etc/ssh/ssh_config
# add or uncomment these two lines
RSAAuthentication yes
PubKeyAuthentication yes
# ... and restart
/etc/init.d/ssh restart

Troubleshooting

A couple of things to keep in mind. 1) Permissions matter. Make sure that your keys are not world readable (this should be secure) Run chmod 400 on authorized_keys file.

If you had a set of keys already setup in .ssh/ on your local machine and want to install the new keys in another directory so as not to overwrite the old pair, you need to add them to ssh with this command

ssh-add ~/full/path/to/your/new/keys

More information is available here http://www.debian-administration.org/articles/152