Following up on J. W. Tanner’s suggestion (now moved to chat, sigh) to use ratios of Pell numbers, you can take
$$a_n=2^n\frac{\bigl((1+2^n)^n+(1-2^n)^n\bigr)\bmod(4^n-2)}{\bigl((1+2^n)^n-(1-2^n)^n\bigr)\bmod(4^n-2)}.$$
To see this, let $p_n,q_n$ be the unique natural numbers such that
$$\tag{$*$}(1\pm\sqrt2)^n=q_n\pm p_n\sqrt2$$
(so $p_n$ are the Pell numbers, and $q_n$ half the Pell–Lucas numbers). On the one hand, $(*)$ implies
$$\begin{align*}
q_n&=\frac{(1+\sqrt2)^n+(1-\sqrt2)^n}{2},\\
p_n&=\frac{(1+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2},
\end{align*}$$
whence
$$\frac{q_n}{p_n}\sim\frac{(1+\sqrt2)^n/2}{(1+\sqrt2)^n/(2\sqrt2)}=\sqrt2.$$
On the other hand, if we put $r=2^n$ and $m=4^n-2$, we have
$$r^2\equiv2\pmod m,$$
hence there is a ring homomorphism $\mathbb Z[\sqrt2]\to\mathbb Z/m\mathbb Z$ that reduces each integer modulo $m$, and maps $\sqrt2$ to $r$. Applying it to $(*)$, we obtain
$$(1\pm r)^n\equiv q_n\pm p_nr\pmod m,$$
whence
$$\begin{align*}
(1+r)^n+(1-r)^n&\equiv 2q_n\phantom r\pmod m,\\
(1+r)^n-(1-r)^n&\equiv 2rp_n\pmod m.
\end{align*}$$
But also $0<p_n<q_n<2^{n-1}$, i.e., $2rp_n,2q_n<m$, thus
$$\begin{align*}
\bigl((1+r)^n+(1-r)^n\bigr)\bmod m&=2q_n,\\
\bigl((1+r)^n-(1-r)^n\bigr)\bmod m&=2rp_n.
\end{align*}$$
That is,
$$a_n=\frac{q_n}{p_n}.$$
Note that nothing special about $r=2^n$ was used in the derivation above; you can take any integer $r$ larger than $(1+\sqrt2)^n$ or so, and $m=r^2-2$.