Don’t blame the user - blame Matrix for designing the system like this.

> They have to be stored somewhere. You want private keys on the public server?

Yes. Encrypted. The feature is called “dehydrated devices” and the Matrix team has been working on it for quite a while now.