Yes, you have to revoke with each service. One of the design elements of U2F is that a site X cannot in any way test or reveal if site Y is registred on the U2F device. Also, its even designed so if someone has 2 accounts on site X, the site X cannot detect that those 2 accounts are stored on the same U2F device.
This to ensure the users privacy so multiple sites cannot track the same user across different sites.
Having a revocation scheme would reveal this fact to the site.
Theres no standarized way of revocation and regeneration, but each site has to implement its own scheme based on security requirements. One scheme can be that using only your username/password, you can revoke your U2F device. To then tie a new U2F device to your account, one scheme could be a physical letter with a one-time code, Another scheme could be SMS in combination with a email. There also possible to issue a revocation certificate.
Or even 2 U2F devices could be tied to the same account at signup, where usage of the second U2F device would disable the first, and then you have to order a third one (that then needs to be activated with the service in question and this third becomes the backup key for the now activated second one).