It's as easy as installing a PAM module, enabling challenge-response for OpenSSH, and then generating a secret.

I set this up yesterday on a an Ubuntu 14.04 vps using this guide: https://www.digitalocean.com/community/articles/how-to-prote...

It's worth noting that private ssh keys work without 2FA and all password logins are required to use 2FA. That's the security policy I was looking for.

Setting up pam_url+totpcgi is bit involved, and it doesn't come prepackaged for Debian. But it certainly shouldn't be insurmountable. Here is link to their installation guide:

https://github.com/mricon/totp-cgi/blob/master/INSTALL.rst

Google Authenticator has a PAM module, and you can use it for SSH.