Generating key pairs

This is what ssh-keygen(1) is for. Use a SSH2 key if at all possible.

ssh-keygen -t dsa

1. or

ssh-keygen -t rsa

Distributing public keys

You need a .ssh directory in your home on the remote machine. This directory must not have permissions set to more than 700. Depending on whether you're using SSH1 or SSH2, keys go into .ssh/authorized_keys or .ssh/authorized_keys2, respectively, which must have its permissions set to no more than 0600. Obviously the directoriy and these files must be owned by the user they belong to. If the permissions are wrong, SSH will refuse to read them (without telling you, unfortunately - it only cries to syslogd(8)). Debian provides a ssh-copy-id(1) program which does all this automagically. Just say

ssh-copy-id hostname

Limit key use to certain machines

You can tell sshd(8) to allow a certain key to be used only by certain hosts by putting the from keyword with a list of globs in front of a key in authorized_keys. Eg

from="*.example.com,localhost" ssh-dss XXXX....base64..keyid....= username@host

This will only allow this key to be used from localhost and hosts in the .example.com domain. You can also prefix a glob with a ! to negate it.

There are lots of other options documented in the sshd(8) manpage.