I don't personally consider it greatly increasing complexity. At account creation I register the Yubikeys at the PC and on my keyring. When I first login from a different PC I use the Yubikey from my keyring to login and then register the Yubikey at this new PC.