It seems that you are not freeing the last rotated image. Check for null, and free the surface before creating a new one:
void Sprite::Rotate(double angleAdd)
{
if(rot != NULL)
SDL_FreeSurface(rot);
rotated = true;
double temp = 0;
angle += angleAdd;
temp = angleAdd + angle;
if (temp >= 360)
angleAdd = temp - 360;
if (temp <= 360)
angleAdd = temp + 360;
rot = rotozoomSurface(image, angle , 1.0, 1);
}