What to Do if You Lose a U2F Key

U2F is widely regarded as the best way to secure your important accounts since it relies on access to a physical key before the account will be unlocked. But what happens if you lose that key?