Naive quedtion perhaps, bit why wouldn't they be able to employ the same hardware on icloud than on the phone?
As above, not a good idea for a default, but don't see why it wouldn't be technically viable for opt-in protection.
To spell it out (1) request new encryption key from device (let's call it key4cloud); (2) encryption key generated, displayed for physical logging by the user, & stored in the secure enclave; (3) all normal backups to iCloud are now encrypted via key4cloud; (4) user loses phone; (5) user purchases new phone; (6) new phone downloads data; (7) user enters key4cloud from physical notes & decrypts backup
Yes, it requires paper and a pencil and user education (hence the opt-in). But it's also incredibly resistant to "Give us all iCloud data on User Y."