Which one do you recommend?
Aegis for Android, Tofu for iOS.
I prefer to keep my 2FA in the cloud in case I lose my devices
Then you should stick with Authy. Backing sensitive data up to the cloud is a bad idea, and backing 2FA codes up the cloud is an even worse idea, but if you want that functionality then you'll have to stick with Authy to do it smoothly. Good 2FA apps do not back up data to the cloud, instead supporting local encrypted back ups only. You could always upload one of these back ups to the cloud, but I wouldn't recommend it.
Can I keep my backup codes in Aegis servers?
Aegis does not have servers. It is all done locally, which is by far the most secure way of doing things.
The problem in doing things locally is that physical back-ups are risky as well.
A few years ago a thief broke into my house and stole my computer, tablet, external HD, and other valuables.
If my 2FA backup was there, I would lose all of them (only my phone survived this incident). I lost all my photos, for example, except those in the cloud (90% of them, thankfully).
My bitcoin private keys are really safe in physical backups and nobody could really find them, but they are very important to me and I am not willing to put the same effort in those 2FA codes.
My 2FA codes are important, but I will just have some headaches if I lose them, I won't really lose any money.
I think RickDeckard suggestion, to encrypt files in the cloud, might be a good idea.
I would really hate to send my KYC documents to Authy if requested, so they could sell them in the black market or to third party.