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/.