Are rotation matrices tensors? If no, why? I'm not sure about it, for example considering the $z$-axis rotation matrix when I rotate the coordinate system the rotation matrix around the old $z$-axis change form.
No, for an Euclidean 3D space the rotations (and translations) are maps between reference frames, while tensors are independent of reference frames. See also my related Phys.SE answer here in the context of SR.