Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

As you pointed out, if $g$ is a primitive root of $n \ge 3$, then the primitive roots must be among $g, g^2, \dots, g^{\varphi(n)-1}$.

To count the exact number, as you observed, we need to show that for $1 \le k \le\varphi(n)-1$, $g^k$ is a primitive root iff $k$ is relatively prime to $\varphi(n)$.

Suppose that $k$ is relatively prime to $\varphi(n)$. Then there exist integers $x$ and $y$ such that $xk=y\varphi(n)+1$. It follows that $(g^k)^x=(g^{\varphi(n)})^y g\equiv g\pmod{n}$. Since $g^{kx}\equiv g\pmod{n}$, for any $e$ we have $$g^e\equiv (g^{kx})^e\equiv (g^k)^{xe}\pmod{n}.$$ It follows that any power of $g$ is congruent to some power of $g^k$. This implies that $g^k$ is a primitive root of $n$.

On the other hand, if $k$ is not relatively prime to $\varphi(n)$, let $d \gt 1$ be a common divisor. Then $(g^k)^{\varphi(n)/d}\equiv 1\pmod{n}$, since $k\varphi(n)/d$ is a multiple of $\varphi(n)$. It follows that $g^k$ has order $\le \varphi(n)/d$, so cannot be a primitive root.

Hint: If $G$ is a cyclic group of order $n$ generated by an element $g$, then the order of the element $g^m$ is $n/\gcd(m,n)$ (you should have seen this result shortly after cyclic groups were introduced). In particular $g^m$ is of order $n$, if and only if $\gcd(m,n)=1$.

For $a^k$ to be a primitive root, you have to show that $1,a^k,a^{2k},\dots,a^{(\phi(n)-1)k}$ are different (modulo $n$). So, show that if $\gcd(k,\phi(n))\ne1$ then these numbers aren't different (easiest way is by showing 1 is repeated), and show that if the gcd is 1 then the numbers are all distinct.