Maybe we're talking about different private keys? To clarify, here's how I think it works:
1) To send you a new iMessage, someone else's iPhone Z encrypts it with your public key and sends it through the iMessage network. Apple can't read this message since they don't have your iMessage private key, which is only on your device.
2) Your iPhone A receives the encrypted iMessages and decrypts them with your iMessage private key on your device.
3) iPhone A stores the decrypted iMessage content in its filesystem, which is encrypted locally with the device private key (derived from your device passcode).
4) Time to backup... iPhone A decrypts its filesystem with your device private key, and sends filesystem contents as plaintext, through an encrypted tunnel, to an iCloud backup server, which encrypts the backup locally with an iCloud server private key, and stores it.
5) You get a new iPhone, let's call it iPhone B. iPhone B asks iCloud for a restore. The iCloud server locally decrypts the backup, and sends it to iPhone B as plaintext through an encrypted tunnel. iPhone B receives the backup as plaintext and stores it locally, encrypting it locally with the device private key.
6) iPhone B iMessage client loads the plaintext old iMessages into the Messages client for you to read.
At no point in this process would Apple have or store your iMessage private key or your device private key.