For $p>3$ the Chinese Remainder Theorem shows that there are integers $k\equiv 11\pmod{24}$ such that $-k$ is not a quadratic residue modulo $p$.