Editing remote files with Emacs using public key authentication

How can I edit files on my remote host using my local Emacs when I can access the remote host only through SSH with public key authentication? Tramp handles normal password logins pretty well but I can't figure out how to get it work with key pairs. I'm using unix/linux on both ends.