The first thing to say is that such numbers exist. The "trivial" cases are where $n = F(n)$, namely $n=1,5$. After that the next solution is $n=12$, and many multiples of $12$ are also solutions. We will show below that infinitely many solutions exist.
The second thing to note is that computing Fibonacci numbers $F(n)$ by the recurrence relation modulo $n$ seems inefficient. These are basically integer powers of the "golden ratio" $\tau = 1.618\ldots$ and its reciprocal, so the computation of $F(n)$ can be done in $O(\log n)$ steps, rather than $n$ (very simple, add/subtract) steps using the recurrence from scratch each time. Knowing that PARI is performing the power of a small matrix mod $n$, it seems like that this is already being taken advantage of...
A sieving idea, using the strong divisibility property of the Fibonacci numbers, seems attractive as well. There should be a lot of structure to solutions of $n|F(n)$ because $m|n \iff F(m)|F(n)$. In particular if $n|F(n)$, and $m=F(n)$, then $m|F(m)$ will be another solution provided $n \gt 5$. This shows an infinite number of solutions exist.
More generally if $m,n$ are solutions, so too will $\operatorname{lcm}(m,n)$ be a solution. I will add more details, but as an example, $5\cdot 12$ is a solution since both $5$ and $12$ are.
I will also show that by looking at prime divisors, a large amount of search space can be pruned away. The simplest case of this is that any solution divisible by $2$ or by $3$ must actually be divisible by $12$. This alone reduces the search space by a little more than half, since we need check only residues $0,1,5,7,11$ mod $12$ for possible solutions.
What we should check is the periodic divisibility of Fibonacci numbers by $n$. It turns out that for each positive integer $n$, there exists a positive integer $a(n)$ such that $n|F(m)$ if and only if $a(n)|m$. See OEIS Sequence A001177 as well as David Speyer's fine Answer (and others) to this Math.SE Question on divisibility in Fibonacci numbers.
Only every third Fibonacci number is even, $a(2)=3$, which implies that if $n$ is an even solution to $n|F(n)$, then also $3|n$, and thus $3|F(n)$. But three divides only every fourth Fibonacci number, $a(3)=4$, so even $n|F(n)$ implies $12|n$. A similar argument starting from a solution where $3|n$ would give again that $12|n$.
Now the prime divisor $5$ is a bit of a wash, because $a(5)=5$. We get no new restrictions by sieving for multiples of $5$.
If we check for larger prime divisors, we do find ever more stringent restictions. Consider a solution $n|F(n)$ such that $7|n$. Thus, since $7|F(n)$ we have also $a(7)=8$ dividing $n$. Since $56 = \operatorname{lcm}(7,8)$ divides $n$ and $F(n)$, we have $a(56)=24$ divides $n$. Taking the least common multiple once more gives us that $168|n$, and now (since $a(168)=24$) the reasoning stabilizes. Note that $168|F(168)$, the first solution divisible by $7$, and to find any solution divisible by $7$, it suffices to check $n$ which are divisible by $168$.
This suggests a scheme in which we compute (or look up) $a(p)$ for all primes $p$ under the square root of the threshold $N$ you wanted to search, e.g. $N=10^{10}$ if I understood the original problem, and we need the primes below $10^5$. We carry out the chain of reasoning for $p$ similar to the case $p=7$ above entails, and that will both find a "primitive" solution and reduce searching for solutions that are multiples of $p$ to searching multiples of what generally is a much larger number.
There is an interesting open problem in mathematics, Wall's conjecture, connected to the computation of $a(p^k)$ for prime $p$ and exponent $k \gt 1$. The search of examples has been carried out in the negative beyond $10^{16}$, which allows us for computational purposes to assume $a(p^k) = p^{k-1} a(p)$. For example, $a(5^k) = 5^{k-1} a(5) = a(5)$ (this is known to be true).
Armed with these insights we should be able to make sense of the families of solutions that appear in our search. For example, if $n|F(n)$ is a solution, and $k$ is any factor of $F(n)/n$, then $kn$ will also be a solution. By "primitive" solutions earlier I meant solutions, such as $12$ and $168$ that do not arise in this fashion, e.g. there is no solution $n$ dividing $12$ (resp. $168$) such that $12/n$ is a factor of $F(n)/n$ (mutatus mutandi for $168$). The search can be refined in this way to a search only for primitive solutions, and it would be interesting to know their frequency.
fibmod. So if instead you kept two variables holding $F_{n-1}$ and $F_n$, then each iteration would only require an addition and a reduction mod $n$, with a bit of shuffling of values to keep the last two Fibonacci numbers for the next iteration. $\endgroup$