> Too slow. RSA encryption is very expensive.

So use a public-key algorithm that is designed to be faster, less expensive, and use smaller keys -- e.g. NaCl's crypto_box, which uses Curve25519 under the hood: https://nacl.cr.yp.to/box.html.

> Also, RSA keys are enormous.

We're talking about devices that have as a primary goal the storage of lots of high-resolution media (photographs and video). I think you could find a couple extra KB to spare for an RSA public key... (although, again, there are better primitives than RSA that should be preferred).