The nice thing is that in the default config you don't need two-factor auth when using public-key auth.
So from your trusted terminal you use public-key auth, and only from untrusted terminals you need to use two-factor auth.
Yubikey - http://www.yubico.com/yubikey - Check out the Github repo for the PAM https://github.com/Yubico/yubico-pam#readme -- Stop by and see me (Nick @ MNX Solutions) at Indiana Linux Fest http://www.indianalinux.org/ we have a few Yubikeys we are giving away.
Duo Security - http://www.duosecurity.com - These guys are doing some neat things in this area: https://github.com/duosecurity/duo_unix
http://itunes.apple.com/us/app/google-authenticator/id388497...
It took 5 minutes to figure out and setup and the price is very right. Looking forward to seeing this get improved.