First install Google Authenticator:

apt-get install libpam-google-authenticator

This works well on Ubuntu (Trusty or newer).

Next, login to your server with the user you’re going to use MFA with, execute google-authenticator and follow the steps as indicated below. You may scan the QR-Code which is shown on the console with your phone (for example using the Google Authenticator App or Authenticator Plus) which is certainly the easiest option as it will be added right away.

Do you want authentication tokens to be time-based (y/n) y|0&cht=qr&chl=otpauth://totp/.....

Do you want me to update your "/root/.google_authenticator" file (y/n) y

Do you want to disallow multiple uses of the same authentication
token? This restricts you to one login about every 30s, but it increases
your chances to notice or even prevent man-in-the-middle attacks (y/n) y

By default, tokens are good for 30 seconds and in order to compensate for
possible time-skew between the client and the server, we allow an extra
token before and after the current time. If you experience problems with poor
time synchronization, you can increase the window from its default
size of 1:30min to about 4min. Do you want to do so (y/n) n

If the computer that you are logging into isn't hardened against brute-force
login attempts, you can enable rate-limiting for the authentication module.
By default, this limits attackers to no more than 3 login attempts every 30s.
Do you want to enable rate-limiting (y/n) y

You can alternatively use the link that is shown right above the QR-Code or add your application manually using the secret code shown in the console.

Now, edit /etc/pam.d/sshd and add this line right at the end:

auth required

Then edit /etc/ssh/sshd_config, find the line containing ChallengeResponseAuthentication and change it to:

ChallengeResponseAuthentication yes

Finally just restart SSH: service ssh restart

And login again! The server will ask you for an additional verification code – additional security to using password or public keys.