I know there are $n(n-1)\over 2$ rotational degrees of freedom in $n$-dimensions, but I am not really sure how to solve this problem.
My intuitive solution to this is to assume that each value represents an angle of rotation on a plane of rotation and are applied in a specific order similar to Euler angles.
$\newcommand{\Reals}{\mathbf{R}}$Attach an orthonormal triple to your rigid object. Its "rotational position" (not including translation) is uniquely determined by an orthonormal triple in $\Reals^{n}$; there are $$ (n - 1) + (n - 2) + (n - 3) = 3n - 6 $$ degrees of freedom: $(n - 1)$ for a point in the unit sphere, $(n - 2)$ for a unit vector orthogonal to the first, and $(n - 3)$ for a unit vector orthogonal to the first two.
Alternatively, there are $\frac{1}{2}n(n - 1)$ rotational degrees of freedom, as you say, but this overcounts because the $(n - 3)$-dimensional space orthogonal to the situated object can be rotated arbitrarily without moving the object. To get the correct count, subtract $\frac{1}{2}(n - 3)(n - 4)$, the number of rotational degrees of freedom of $\Reals^{n - 3}$, obtaining $$ \tfrac{1}{2}\bigl[n(n - 1) - (n - 3)(n - 4)\bigr] = \tfrac{1}{2}\bigl[n^{2} - n - (n^{2} - 7n + 12)\bigr] = 3n - 6. $$
