Your explanation is correct. I have a remark that the inequality you want to prove is indeed an equality.
Let $C_n$ denote the cyclic group of order $n$. The group $G:=\text{Aut}\left(D_n\right)$ is isomorphic to the semidirect product $H:=C_n\rtimes \text{Aut}\left(C_n\right)$, where
$$\left(c_1,f_1\right)\cdot \left(c_2,f_2\right):=\big(c_1\,f_1\left(c_2\right),f_1\circ f_2\big)$$
for all $c_1,c_2\in C_n$ and $f_1,f_2\in\text{Aut}\left(C_n\right)$. If $C_n$ is generated by $c$, then each element of $\text{Aut}\left(C_n\right)$ sends $c$ to $c^k$ for some $k=1,2,\ldots,n$ with $\gcd(k,n)=1$, and we write $\gamma_k$ for this element of $\text{Aut}\left(C_n\right)$.
The reason that $G$ is isomorphic to $H$ is as follows. Let $$D_n=\left\langle r,s \,|\,r^n=s^2=1\text{ and }rs=sr^{-1}\right\rangle=\left\{1,r,r^2,\ldots,r^{n-1},s,rs,r^2s,\ldots,r^{n-1}s\right\}\,.$$
Hence, for each $\tau\in G$, it suffices to look at $r_\tau:=\tau(r)$ and $s_\tau:=\tau(s)$. We have $r_\tau=r^{k}$ and $s_\tau=r^{j}s$ for some $k=1,2,\ldots,n$ with $\gcd(k,n)=1$ and for any $j=0,1,2,\ldots,n-1$. Thus, we write $\tau_{j,k}$ for this automorphism $\tau$. Then, the map $\psi:G\to H$ sending $\tau_{j,k}$ to $\left(c^j,\gamma_k\right)$ is a group isomorphism. That is,
$$\big|\text{Aut}\left(D_n\right)\big|=|G|=|H|=\left|C_n\right|\,\big|\text{Aut}\left(C_n\right)\big|=n\,\phi(n)\,.$$
You have to fill in a lot of gaps I intentionally left out, of course.
P.S. Interestingly, the condition $n>2$ is important. It turns out that $D_2\cong C_2\times C_2$ is extraordinary. That is, $$\text{Aut}\left(D_2\right)\cong\text{Aut}\left(C_2\times C_2\right)\cong \text{GL}_2\left(\mathbb{F}_2\right)\cong S_3\,,$$
where $S_3$ is the symmetric group on $3$ symbols.
Best Answer
Note that $\phi(a^n - 1)$ measures the number of automorphisms of $\mathbb{Z}/(a^n - 1)\mathbb{Z}.$ There is a subgroup of order $n$ in this group: if $\phi$ is the automorphism sending $1$ to $a,$ then $\phi$ generates a subgroup of order $n.$ The statement follows from Lagrange's Theorem.