It is easy to verify that $\left(\dfrac{5}{p} \right) = \left(\dfrac{p}{5}\right)$. We know that $\left(\dfrac{p}{5} \right) =1$ when $p$ is quadratic residue modulo $5$. So $p = 1\pmod 5$ or $4 \pmod 5$. Therefore, for every prime $p$ in the arithmetic progression $1+5j, 5$ is residue. Similarly, for every prime $p$ in the progression $4+5j, 5$ is residue.
We know from Diritchlet theorem that there are infinitely many primes any arithmetic progression $a+bj$, for fixed co-prime pair $(a,b)$. So just search for first few primes in the progressions $1+5j, 4+5j$. (You can see that first few primes with this property are $11, 41, 29$, ...etc).
To my knowledge, there is no algorithm that performs better than brute force technique for finding primes in the given arithmetic progression.