Besides Beeper, the only consumer bridge hosting service I'm aware of is Element One, but it's only barely maintained, so I'd definitely recommend self-hosting over that.
Messages are stored in encrypted form on the Beeper server and the Beeper client has a local search index (the same one used by Element desktop: https://github.com/matrix-org/seshat)
This step is very straightforward; append the public key to
authorized_keys as you would normally. Note that U2F keys are a new
OpenSSH key type, so the server must support it too.
I guess it will take a few years until all servers are upgraded.
Besides Beeper, the only consumer bridge hosting service I'm aware of is Element One, but it's only barely maintained, so I'd definitely recommend self-hosting over that.