Using QR decomposition to generate small random rotations? I found the recipe below to work for generating random rotation matrices  in n dimensions. (straightforward modification from CUE sampling recipe from page 11 of https://arxiv.org/abs/math-ph/0609050). Is there a similarly efficient algorithm to generate small rotations? (ie, I want the vectors before and after transformation to be close in some sense)
randomRotation[n_]:=Module[{M,z,q,r,d,ph},
z=RandomVariate[NormalDistribution[0,1],{n,n}];
{q,r}=QRDecomposition[z];
d=Diagonal[r];
ph=d/Abs[d];
M=q*ph;
(* Note, determinant may be -1 giving "pseudo-rotation", switch 2 rows of the matrix to guarantee true rotation *)
indices=If[Det[M]>0,Range[n],{2,1}~Join~Range[3,n]];
M[[indices]]
];

 A: You obtain Haar-uniform random rotations if you perform QR decomposition on an initial matrix which has independent and identically gaussian distributed random elements. 
If you want random small rotations from QR, you could perform it on initial matrices which consist of random small perturbations of the identity. 
A: If you mean by "nD rotation" an orthogonal transformation with unit determinant, here is a simple recipe with a low computational complexity.
a) Principle: obtain it by a composition of two hyperplane reflections (aka symmetries) with rather close normal vectors (see remark 1).
b) Matrix version: You probably know that reflection with respect to an hyperplane with unit normal (column) vector $N$ is rendered by a Householder matrix $I_n-2NN^T$ (https://en.wikipedia.org/wiki/Householder_transformation). Thus, the rotation matrix is $$(I_n-2N_1N_1^T)(I_n-2N_2N_2^T)$$ where $N_2$ for example is a perturbation of $N_1$.
Remark 1: As remarked by @Rahul, this leaves a $(n-2)$ hyperplane invariant. In order to obviate this lack of generality, it suffices to apply again and again transformations $$(I_-2N_{2k+1}N_{2k+1}^T)(I_n-2N_{2k+2}N_{2k+2}^T)$$ for $k=1\cdots [n/2]$.
Remark 2: Principle a) generalizes a well known property of planar geometry (Composition of two reflections is a rotation): the composition of a reflection with respect to  line $y=\tan(\alpha)x$, with a reflection with respect to line $y=\tan(\beta)x$ is a rotation with angle $2(\beta-\alpha)$.
Remark 3: in 3D, one can also consider Rodrigues' formula (https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula).
Remark 4: Vector $N$ is an eigenvector associated to the Householder matrix with eigenvalue $-1$.
