SDL_gfx is indeed incredibly slow, and with SDL 1.2 (which I see you're using), only multiples of 90 degree rotations have acceptable performance.
SDL 2.0 has hardware accelerated surfaces, though (called SDL_Texture; SDL_SWSURFACE, SDL_HWSURFACE, etc. are deprecated, I believe). SDL_Textures can be blit with a rotation applied to them, or just rendered normally.
//Renders a hardware-accelerated texture to the destination renderer
int SDL_RenderCopy(SDL_Renderer* renderer, SDL_Texture* texture,
const SDL_Rect* srcrect, const SDL_Rect* dstrect);
//Renders a hardware-accelerated texture with optional rotation and/or flipping applied
int SDL_RenderCopyEx(SDL_Renderer* renderer, SDL_Texture* texture,
const SDL_Rect* srcrect, const SDL_Rect* dstrect,
const double angle, const SDL_Point* center,
const SDL_RendererFlip flip);
It's not too different from SDL 1.2, with the main differences being that you now have SDL_Window and SDL_Renderer instead of something like SDL_Surface* screen = SDL_SetVideoMode() (which is also deprecated).
SDL_Window* window = SDL_CreateWindow("My Game", 0, 0, 640, 480, SDL_WINDOW_SHOWN);
SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
SDL_Surface* surface = IMG_Load("MyLovelyImage.png");
SDL_Texture* texture = SDL_CreateTextureFromSurface(renderer, surface);
SDL_FreeSurface(surface);
SDL_Point center = {16, 16};
SDL_RenderCopyEx(renderer, texture, 0, 0, 45, ¢er, SDL_FLIP_HORIZONTAL);
SDL_RenderPresent(renderer);
Considering SDL_Textures are
solely primarily (they might exist outside of hardware memory if you're out of it) hardware textures, I would imagine that this is a hardware-accelerated process and wouldn't be as painfully slow as SDL_gfx. I haven't run any tests to see if it's significantly faster or close enough to OpenGL (I'm too lazy to compile the latest version of SDL_image and can't run OpenGL. Go me), although you might find this to be acceptable compared to switching completely to OpenGL rendering. It's another option if your hardware can't handle the newer versions of OpenGL, at least (Intel, you suck).