Also I don't know how calculating sin/cos every frame would consume the processing power. I am afraid it would be pretty devastating for the processor (creating a mobile game).

First question: what happened when you tried it? That is, a general rule for any app development is to optimize only when it's needed. Do you need to improve your method for performance purposes?

IF your app's performance needs to be improved, the process for determining where your code needs to be revised is called profiling. The possibility exists that the calculations you think may be the culprit may, in fact, not be where your app is inefficient. There's no sense in rewriting a section of code for optimization if that's not where optimization is needed. In your case, for instance, better gains may be had by culling collision possibilities with AABBs or bounding spheres. It may turn out that, by doing so, your sine/cosine functions calls may only be needed once per update and you needn't optimize that code.

If you're concerned with your app's performance, you should learn the profiling process. There are tools available for doing just that which you may be able to find by googling for something like (e.g.) "mobile apps profiling." For mobile apps, you may also be concerned with battery consumption, and the results of a google search should provide information in that regard, also.

Just recalculate the vertices with the new angle - but you need to keep track of your original vertices!

or

Add two unit vectors to every sprite which defines the rotation for X and Y and use these for the axis-test based on projection (Separating Axis Theorem). Calculating the local projection is done like this:

function RectShape(x, y, w, h) {
  this.pos = new Vec2(x, y);
  this.size = new Vec2(w, h);
  this.axis = [new Vec2(1, 0), new Vec2(0, 1)];
}

RectShape.prototype.project = function (axis) {
  var p = Math.abs(axis.dot(this.axis[0])) * this.size.x * 0.5 + Math.abs(axis.dot(this.axis[1])) * this.size.y * 0.5;
  return new Vec2(-p, p);
};

When you rotate your sprites, you just need to update this two unit vectors:

this.axis[0].set(Math.cos(angle), Math.sin(angle));
this.axis[1].set(-Math.sin(angle), Math.cos(angle));

Dont worry about performance, cos and sin are fast... most languages use CPU optimizations for that.