It is not very difficult to find large strong primes, for whatever definition is used.
The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).
That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or a generator of primes order $q=(p-1)/2$.
Conjecturally, about one integer near $n$ out of $\log(n)^2$ is a safe prime per that definition, and we are expected to find a a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of 20.
In an RSA context, the definition of safe prime varies.
The original RSA article recommended, for some vague definition of large, that
- $p$ is a large prime,
- $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
- and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).
Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).
Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for 512-bit primes or/and multiprime RSA, when an adversary would be content with factoring extremely many public moduli.
Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex.