Essa é uma daquelas que é fácil mas o cara nunca lembra como fazer, já precisei disso algumas vezes e sempre tinha que recorrer ao seu Google para descobrir.

1

  ssh user@host 'mkdir ~/.ssh; echo '`cat ~/.ssh/id_rsa.pub`' >> ~/.ssh/authorized_keys'

Retirado daqui: http://snippets.dzone.com/posts/show/2335

UPDATE: O kbmurata comentou no twitter que algum server/client de ssh pode reclamar das permissões da pasta .ssh, se isso acontecer, rode:

1

  chmod 700 ~/.ssh