A partial result: any FPA mus be congruent to $2, 3 \bmod 5$, and these primes have density $\frac{1}{2}$ in the set of all primes by the strong form of Dirichlet's theorem.
First, I claim that Binet's formula $F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$ (my numbering differs from yours), where $\phi, \varphi$ are the two roots of $x^2 = x + 1$, is valid modulo $p$ for any prime $p \neq 5$, where $\phi, \varphi$ are interpreted as elements of the splitting field of $x^2 = x + 1$ over $\mathbb{F}_p$. The proof is the same proof as in the usual case, the point being that the discriminant of $x^2 = x + 1$ is $5$, so for any other prime there are two distinct roots. Moreover, since $(\phi - \varphi)^2 = 5$, we know that $\phi - \varphi \neq 0$ for any such prime. It follows that $F_n \equiv 0 \bmod p$ if and only if $\phi^n \equiv \varphi^n \bmod p$.
If $\left( \frac{5}{p} \right) = 1$, then $x^2 = x + 1$ splits over $\mathbb{F}_p$, from which it follows that $\phi^{p-1} \equiv \varphi^{p-1} \equiv 1 \bmod p$, hence that
$$F_{p-1} \equiv 0 \bmod p.$$
By quadratic reciprocity, $\left( \frac{5}{p} \right) = \left( \frac{p}{5} \right)$, hence these are precisely the primes $p \equiv 1, 4 \bmod 5$. So none of these primes are FPAs.
If $\left( \frac{5}{p} \right) = -1$, then $x^2 = x + 1$ has splitting field $\mathbb{F}_{p^2}$. The Galois group is generated by the Frobenius map $x \mapsto x^p$, hence $\phi^p \equiv \varphi \bmod p$ and, similarly, $\varphi^p \equiv \phi \bmod p$, hence $\phi^{p+1} \equiv \phi \varphi \equiv \varphi^{p+1} \equiv -1$, from which it follows that
$$F_{p+1} \equiv 0 \bmod p.$$
This occurs if and only if $p \equiv 2, 3 \bmod 5$.
Edit: Second partial result: any FPA must be congruent to $3 \bmod 4$. Now the density has been reduced to $\frac{1}{4}$. To see this, note that since $\phi \varphi = -1$, the condition that $\phi^n \equiv \varphi^n \bmod p$ is equivalent to the condition that $(-\phi^2)^n \equiv 1 \bmod p$. On the other hand, we know that when $p \equiv 2, 3 \bmod 5$ we have $\phi^{p+1} \equiv -1 \bmod p$, hence
$$\left( - \phi^2 \right)^{ \frac{p+1}{2} } \equiv (-1)^{ \frac{p-1}{2} } \bmod p.$$
It follows that when $p \equiv 1 \bmod 4$ we have
$$F_{ \frac{p+1}{2} } \equiv 0 \bmod p.$$
I don't expect these necessary conditions to be sufficient. The question is similar to asking that $- \phi^2$ behave like a primitive root, so this question or a variation on it may end up being an open problem.
Edit #2: For example, you can verify for yourself that $F_{16} \equiv 0 \bmod 47$ even though $47 \equiv 2 \bmod 5$ and $47 \equiv 3 \bmod 4$.
Yes, this method is valid (in particular, your reasoning that the numbers you come up with are prime is correct), but it's not likely to be particularly effective.
I'm going to assume familiarity with big- and little-O notation; if you aren't familiar with this, Wikipedia is a good resource.
The key issue that makes this not very effective is the $\sqrt{a-b}\leq p_n$ condition. This means that, if you want to find a prime that's about $X$, you need to know all the primes less than $\sqrt X$. This essentially means that trial division would work fine (since this is all you need for trial division), as would something like the Sieve of Eratosthenes.
The other thing is that, as $n$ gets big, the condition that $\sqrt{a-b}\leq p_n$ becomes really hard to satisfy. Consider the product
$$P_x=p_1p_2\cdots p_n$$
of all primes less than some number $x$. It is known that this product is $e^{x(1+o(1))}$. You're looking for a divisor $a$ of this product so that
$$0\leq a-\frac{P_x}{a}\leq x^2.$$
Solving for $a$, this becomes
$$0\leq a^2-P_x\leq ax^2\Leftrightarrow \sqrt{P_x}\leq a\leq \frac{x^2+\sqrt{x^2+4P_x}}{2}=\frac{x^2}2+\sqrt{P_x+\frac{x^2}4}.$$
The issue is that, as $x$ is large, $P_x$ is much larger than $x^2$, and so
$$\sqrt{P_x+\frac{x^2}4}\leq \sqrt{P_x}+1.$$
This essentially means any product $a$ has to lie in a range around $\sqrt{P_x}$ of size about $x^2$. Because there are $2^n\ll P_x$ divisors of $P_x$, it seems unlikely that many of them will be so close to $\sqrt{P_x}$, and so for many large primes this technique may not give any numbers at all.
Best Answer
Write $F_n$ for the $n$-th Fibonacci number. For $n\geq 2$, $F_n$ is the nearest integer to $((1+\sqrt{5})/2)^n/\sqrt{5}$.
Fix a positive integer $k$. The Prime Number Theorem suggests that the probability that $k+F_n$ is prime is about $$ \frac{1}{\log\left(k+\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right)}. $$ The sum of these probabilities for $n\geq 2$ diverges to $+\infty$ (the $n$-th term is comparable to $n^{-1}$), so we should expect that for each $k$ there are infinitely many values of $n$ for which $k+F_n=p$ is prime. For these $n$, we can write $k=p-F_n$.
Of course this is just a heuristic. There might be some reason $k+F_n$ is more or less likely to be prime than a randomly chosen integer of about the same size. But unless there is a good reason to the contrary, we should expect that every positive integer can be written as $p-F_n$ for some prime $p$ and Fibonacci number $F_n$. That said, statements like this are sometimes very hard to prove.