Not necessarily. Let $F_k$ be the regular Fibonacci sequence. Then we have $\text{fib}_{n, x_0, x_1}(k)=x_0F_{k+1}+(x_1-x_0)F_k\mod n$. Letting $\pi(n)$ be the $n$th [Pisano period](https://en.wikipedia.org/wiki/Pisano_period), this implies that $\text{fib}_{n, x_0, x_1}$ is periodic with period dividing $\pi(n)$. There are plenty of numbers, for instance all numbers modulo which $x^2-x-1$ has a root (as by Binet's formula and Euler's theorem we then have $\pi(n)\mid\varphi(n)<n$).