In an ideal E2E encrypted system the private keys should never be readable outside the systems you trust. The keys can be encrypted using personal credentials (like a password) and stored on the cloud. A simplified login flow looks like this: 1. download your encrypted keychain, 2. decrypt it using your personal credentials, 3. fetch encrypted data and decrypt it using your keychain.

But you still have to trust the application that does all this behind the screen to not leak your decrypted keychain or personal credentials. Facebook's messenger app is closed source so who knows that's happening there.