Para gerar o par de chaves, use (no cliente) o comando:
$ ssh-keygen -t rsa
Ele deve ser executado usando seu login de usuário (o mesmo que você usa para acessar os servidores remotos), não como root:
Generating public/private rsa key pair. Enter file in which to save the key (/home/morimoto/.ssh/id_rsa): Created directory '/home/morimoto/.ssh'. Enter passphrase (empty for no passphrase): ******** Enter same passphrase again: ******** Your identification has been saved in /home/morimoto/.ssh/id_rsa. Your public key has been saved in /home/morimoto/.ssh/id_rsa.pub. The key fingerprint is: ff:28:26:f6:87:67:9f:4c:9a:c8:0a:3b:21:81:88:b4 morimoto@athenas
A passphrase pode ser desde uma senha "normal", com de 8 ou 12 caracteres, até uma frase complexa, sem limite de tamanho. O importante é que não seja algo fácil de adivinhar. A passphrase é, na verdade, um componente da chave de encriptação; sem ela é impossível usar a chave.
O comando gerará os arquivos ".ssh/id_rsa" e ".ssh/id_rsa.pub" dentro do seu diretório home, que são, respectivamente, sua chave privada e sua chave pública. O ".ssh/id_rsa" é um arquivo secreto, que deve usar obrigatoriamente o modo de acesso "600" (que você define usando o chmod), para evitar que outros usuários da máquina possam lê-lo. Muitos servidores recusam a conexão caso os arquivos estejam com as permissões abertas.
Depois de gerar seu par de chaves, falta o comando final, que instala a chave pública no servidor, permitindo que ela seja usada para autenticação:
$ ssh-copy-id -i ~/.ssh/id_rsa.pub login@servidor