I'm not sure the SR is really that large of a paradigm shift.

All Einstein did, I know that conceptually this was a large leap and just saying "all he did" is doing him a severe disservice for his contributions, is note that the mass of an object is dependent upon the speed of the object. Such that for velocities that are not an appreciable fraction of c we can use Newton's laws of gravitation perfectly well.

TLDR; Einstein did not replace Newton, he tweaked him.