It has been a while since I've dug thru the DoC EAR, but from what I remember -- and what I seem to glean from digging thru your link to the Fed Reg -- is that most of this applies only if you're using proprietary encryption. The use of open source algorithms where you provide the relevant source code, such as using AES, Blowfish, or TwoFish, is an exemption.
To be clear, I'm talking about mass market stuff which gets the MMKT designation, nor crypto gear primarily sold to foreign governments.
If using only the published, open source stuff for crypto, then the exporter has only to file the paperwork. The 30-day delay was removed, and there is no real "review request", the paperwork is just on file.
RSA fits the bill just fine, and there is no restriction that I can find for using ginormous keys -- 4,096 bits and beyond.
Feel free to use Elliptic Curve instead of RSA, avoiding Dual EC DRBG (obviously) and the NIST recommended curves if you're paranoid.
I understand that exporting certain hardware requires paperwork, but I'm firmly in the camp of thinking that states "proprietary encryption should be avoided at all costs".