Seems we have VSD customers who used old OpenPGP Keys with RSA 2048.

Standard procedure on changing a key would be to revoke the old key and distribute the public key together with that of the new compliant key.
But as you get the error message "invalid public key algorithm" when trying to use the key, you can not even revoke it.

I believe at least revocation should still be possible. How can we do that?

Personally I would prefer it if keys with algorithms not approved by the BSI would be usable if you acknowledge something like "I know this is not VS-NfD compliant".