One way to solve this problem is Key Transparency, which aims to provides a mechanism to verify that you're receiving a legitimate key, somewhat analogous to Certificate Transparency.

We've implemented this at Proton: https://proton.me/support/key-transparency (although it's still in beta, and opt-in for now - but obviously the aim is to enable it by default).

There's also a (relatively new) working group at the IETF, to work on standardizing (a version of) this: https://datatracker.ietf.org/wg/keytrans/about/.

Then you might want to change email providers.

Really paranoid folks could set up services online that check for this, but I kind of doubt it would happen very often because it would be a major stink for that email service if they were caught, and catching them isn't that hard.