One more thing. If you still have the old phone, and you have not logged out of the client that you used, open the app there and it will send the keys to your old device, but only for the messages for which your new device has noticed that it doesn’t have the keys.

To get all the keys through to the new phone, the easiest is to set up secure backup once (on any of them), and then verify both devices.
If it does not happen instantly, go to the “security & privacy” menu and it’s “encrypted messages recovery” on your old phone, and have a look at what it says. It should say “all keys backed up” in the second row.
When that’s the case, click “restore from backup” in the same menu on the new phone.