By the normal basis theorem, there exists $a \in \mathbb F_{q^n}$ such that $\{\sigma(a)\mid \sigma \in \operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)\}$ spans $\mathbb F_{q^n}$ as $\mathbb F_q$-vector space. Since $\operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)$ is generated by Frobenius, this means that $\mathbb F_{q^n}$ is spanned by the Frobenius powers of $a$, i.e. is generated as $\mathbb F_q[X]$-module by $a$.

Thus $\mathbb F_{q^n} \cong \mathbb F_q[X]/I$, where $I = (\operatorname{Ann}(a))$. Since $\mathbb F_{q^n}$ is killed by $X^n - 1$, we get $(X^n - 1) \subseteq I$. But $$|\mathbb F_q[X]/(X^n-1)| = q^n = |\mathbb F_{q^n}| = |\mathbb F_q[X]/I|,$$ so the inclusion $(X^n - 1) \subseteq I$ has to be an equality. That is, $$\mathbb F_{q^n} \cong \mathbb F_q[X]/(X^n-1),$$ as $\mathbb F_q[X]$-modules. The result now follows from the following lemma.

Lemma. Let $R$ be a PID, let $M = R/(f)$ for some $f \in R\setminus\{0\}$, and let $m \in M$. If $\operatorname{Ann}(m) = (g)$, then there exists $h \in R$ such that $gh = f$, and there exists $n \in M$ such that $hn = m$.

Proof. The first statement follows from the fact that $(f) \subseteq (g)$ since $\operatorname{Ann}(M) \subseteq \operatorname{Ann}(m)$. For the second statement, note that the sequence $$0 \to (h)/(f) \to R/(f) \to R/(h) \to 0$$ is exact. But multiplication by $g$ induces an isomorphism $R/(h) \to (g)/(f)$. Hence, the sequence above turns into $$0 \to (h)/(f) \to R/(f) \stackrel{\cdot g}\longrightarrow (g)/(f) \to 0.$$ This proves the second statement: if $gm = 0$, then $m$ is divisible by $h$. $\square$

Remark. I was trying to find a proof that does not use theorems from Galois theory, but I was unable to do so. The only thing you have to prove is that $\mathbb F_{q^n}$ is a cyclic $\mathbb F_q[X]$-module; I used the normal basis theorem to do that. Presumably, the normal basis theorem is exactly the thing you were trying to prove, so my proof is a bit useless for you.

However, a more careful analysis along the same lines could work if you use the structure theorem of finite torsion modules over a PID. Then you might have to do some case separations.

By the normal basis theorem, there exists $a \in \mathbb F_{q^n}$ such that $\{\sigma(a)\mid \sigma \in \operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)\}$ spans $\mathbb F_{q^n}$ as $\mathbb F_q$-vector space. Since $\operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)$ is generated by Frobenius, this means that $\mathbb F_{q^n}$ is spanned by the Frobenius powers of $a$, i.e. is generated as $\mathbb F_q[X]$-module by $a$.

Thus $\mathbb F_{q^n} \cong \mathbb F_q[X]/I$, where $I = (\operatorname{Ann}(a))$. Since $\mathbb F_{q^n}$ is killed by $X^n - 1$, we get $(X^n - 1) \subseteq I$. But $$|\mathbb F_q[X]/(X^n-1)| = q^n = |\mathbb F_{q^n}| = |\mathbb F_q[X]/I|,$$ so the inclusion $(X^n - 1) \subseteq I$ has to be an equality. That is, $$\mathbb F_{q^n} \cong \mathbb F_q[X]/(X^n-1),$$ as $\mathbb F_q[X]$-modules. The result now follows from the following lemma.

Lemma. Let $R$ be a PID, let $M = R/(f)$ for some $f \in R\setminus\{0\}$, and let $m \in M$. If $\operatorname{Ann}(m) = (g)$, then there exists $h \in R$ such that $gh = f$, and there exists $n \in M$ such that $hn = m$.

Proof. The first statement follows from the fact that $(f) \subseteq (g)$ since $\operatorname{Ann}(M) \subseteq \operatorname{Ann}(m)$. For the second statement, note that the sequence $$0 \to (h)/(f) \to R/(f) \to R/(h) \to 0$$ is exact. But multiplication by $g$ induces an isomorphism $R/(h) \to (g)/(f)$. Hence, the sequence above turns into $$0 \to (h)/(f) \to R/(f) \stackrel{\cdot g}\longrightarrow (g)/(f) \to 0.$$ This proves the second statement: if $gm = 0$, then $m$ is divisible by $h$. $\square$

By the normal basis theorem, there exists $a \in \mathbb F_{q^n}$ such that $\{\sigma(a)\mid \sigma \in \operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)\}$ spans $\mathbb F_{q^n}$ as $\mathbb F_q$-vector space. Since $\operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)$ is generated by Frobenius, this means that $\mathbb F_{q^n}$ is spanned by the Frobenius powers of $a$, i.e. is generated as $\mathbb F_q[X]$-module by $a$.

Thus $\mathbb F_{q^n} \cong \mathbb F_q[X]/I$, where $I = (\operatorname{Ann}(a))$. Since $\mathbb F_{q^n}$ is killed by $X^n - 1$, we get $(X^n - 1) \subseteq I$. But $$|\mathbb F_q[X]/(X^n-1)| = q^n = |\mathbb F_{q^n}| = |\mathbb F_q[X]/I|,$$ so the inclusion $(X^n - 1) \subseteq I$ has to be an equality. That is, $$\mathbb F_{q^n} \cong \mathbb F_q[X]/(X^n-1),$$ as $\mathbb F_q[X]$-modules. The result now follows from the following lemma.

Lemma. Let $R$ be a PID, let $M = R/(f)$ for some $f \in R\setminus\{0\}$, and let $m \in M$. If $\operatorname{Ann}(m) = (g)$, then there exists $h \in R$ such that $gh = f$, and there exists $n \in M$ such that $hn = m$.

Proof. The first statement follows from the fact that $(f) \subseteq (g)$ since $\operatorname{Ann}(M) \subseteq \operatorname{Ann}(m)$. For the second statement, note that the sequence $$0 \to (h)/(f) \to R/(f) \to R/(h) \to 0$$ is exact. But multiplication by $g$ induces an isomorphism $R/(h) \to (g)/(f)$. Hence, the sequence above turns into $$0 \to (h)/(f) \to R/(f) \stackrel{\cdot g}\longrightarrow (g)/(f) \to 0.$$ This proves the second statement: if $gm = 0$, then $m$ is divisible by $h$. $\square$

Remark. I was trying to find a proof that does not use theorems from Galois theory, but I was unable to do so. The only thing you have to prove is that $\mathbb F_{q^n}$ is a cyclic $\mathbb F_q[X]$-module; I used the normal basis theorem to do that.

By the normal basis theorem, there exists $a \in \mathbb F_{q^n}$ such that $\{\sigma(a)\mid \sigma \in \operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)\}$ spans $\mathbb F_{q^n}$ as $\mathbb F_q$-vector space. Since $\operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)$ is generated by Frobenius, this means that $\mathbb F_{q^n}$ is spanned by the Frobenius powers of $a$, i.e. is generated as $\mathbb F_q[X]$-module by $a$.

Thus $\mathbb F_{q^n} \cong \mathbb F_q[X]/I$, where $I = (\operatorname{Ann}(a))$. Since $\mathbb F_{q^n}$ is killed by $X^n - 1$, we get $(X^n - 1) \subseteq I$. But $$|\mathbb F_q[X]/(X^n-1)| = q^n = |\mathbb F_{q^n}| = |\mathbb F_q[X]/I|,$$ so the inclusion $(X^n - 1) \subseteq I$ has to be an equality. That is, $$\mathbb F_{q^n} \cong \mathbb F_q[X]/(X^n-1),$$ as $\mathbb F_q[X]$-modules. The result now follows from the following lemma.

Lemma. Let $R$ be a PID, let $M = R/(f)$ for some $f \in R\setminus\{0\}$, and let $m \in M$. If $\operatorname{Ann}(m) = (g)$, then there exists $h \in R$ such that $gh = f$, and there exists $n \in M$ such that $hn = m$.

Proof. The first statement follows from the fact that $(f) \subseteq (g)$ since $\operatorname{Ann}(M) \subseteq \operatorname{Ann}(m)$. For the second statement, note that the sequence $$0 \to (h)/(f) \to R/(f) \to R/(h) \to 0$$ is exact. But multiplication by $g$ induces an isomorphism $R/(h) \to (g)/(f)$. Hence, the sequence above turns into $$0 \to (h)/(f) \to R/(f) \stackrel{\cdot g}\longrightarrow (g)/(f) \to 0.$$ This proves the second statement: if $gm = 0$, then $m$ is divisible by $h$. $\square$

Remark. I was trying to find a proof that does not use theorems from Galois theory, but I was unable to do so. The only thing you have to prove is that $\mathbb F_{q^n}$ is a cyclic $\mathbb F_q[X]$-module; I used the normal basis theorem to do that. Presumably, the normal basis theorem is exactly the thing you were trying to prove, so my proof is a bit useless for you.

However, a more careful analysis along the same lines could work if you use the structure theorem of finite torsion modules over a PID. Then you might have to do some case separations.