Disclaimer: This guide changes the default PAM configuration which has the potential to lock you out of your computer. I take no responsibility for any badness that results from these instructions. As always, back up all files before changing them, have a live disk ready to revert changes if required and research anything you are unsure of to understand what is happening.
I have tested this with a YubiKey 4 and confirm it works. It should work with any security key that supports the U2F spec including most YubiKeys.

This is based on the Yubico guide with some changes to the scope of protection.

1. Install U2F tools from the Yubico PPA

First, enable the Yubico PPA and install the U2F PAM module:

sudo add-apt-repository ppa:yubico/stable && sudo apt-get update
sudo apt-get install libpam-u2f

2. Configure your key(s)

The Yubico guide creates the configuration in your home directory, but if your home directory is encrypted, you will be unable to access that on a reboot. To get around this, we need to create the configuration somewhere that isn't encrypted. This is up to personal preference, but here we'll create it under /etc.

pamu2fcfg | sudo tee /etc/u2f_keys

When your device flashes, touch the contact to associate the key with your account.

If you wish to add further keys to your account, then run the following command instead:

pamu2fcfg -n | sudo tee -a /etc/u2f_keys

(Having more than one key is a good idea: if your primary key gets lost or damaged, you still have access to your account using the other key(s).)

3. Test your key configuration

To test this configuration we will first enable it for the sudo command only. Remove the key from the computer and edit /etc/pam.d/sudo:

sudo nano /etc/pam.d/sudo

Add the following line below @include common-auth:

auth       required   pam_u2f.so authfile=/etc/u2f_keys

Open a new terminal window, and run sudo echo test. You will be prompted for your password, and then the command will fail. This is expected as your key is not in the computer.

Insert your key, run sudo echo test again. Enter your password and touch your key when it prompts for a touch, after which the your terminal should echo test.

This confirms a good configuration and we can continue to enable this for all authentication. Edit /etc/pam.d/sudo again, and remove the line we added.

4 Enabling 2FA for all authentication

This is the point where we deviate from the Yubico guide, as that covers enabling 2FA for GDM only, whereas we want to enable it for all authentication including TTY, SSH, sudo etc. First we need to edit /etc/pam.d/common-auth:

sudo nano /etc/pam.d/common-auth

Add the following line at bottom of the file:

auth    required   pam_u2f.so nouserok authfile=/etc/u2f_keys cue

• nouserok means that a user without an associated key will not be prompted for 2FA and as such will still be able to log in. If you omit this option, then a user with no key will not be able to log in.
• authfile tells the module to look for the file in /etc rather than the default location (home directory).
• cue will prompt for a touch with a message ("Please touch the device").

(See Yubico's documentation for full list of options.)

At this point, we are finished. Any login attempt will be required to use a key for 2FA. The following is optional.

5. Disabling 2FA for sudo

Personally, I didn't want to have to use my key to run sudo. Disabling it was quite simple, though a bit messy. I am unsure of if there is a better way to do this. Edit the sudo pam file again:

sudo nano /etc/pam.d/sudo

Remove the line that says @include common-auth. Next, copy and paste the contents of /etc/pam.d/common-auth in the same place as the line we removed, but remove the line we added before enabling the U2F module. This last point is crucial: if you leave that line in, you will still need a key to run sudo. Removing that line removes the need for the key to run sudo.

You can adapt this procedure if you want to disable 2FA for ssh or other authentication scenarios. If you run ls /etc/pam.d, it will show the available files: each is named after the scenario that they control. Once again, don't do this unless you know what you are doing and backup files before you make changes.

6. Securing physical access

Of course, anyone can disable this by booting up with a live cd/USB drive and reverting your changes, so if your threat model includes physical access, you will want to enable full system encryption, disable USB/CD booting and set a BIOS password or another method to prevent third parties from tampering. Remember, you are only as safe as the weakest link in your configuration.