Rotation in SDL is done in software(rotozoom). So it's inherently slow

I would recommend either using precalculated rotated surfaces, no rotation or OpenGL