It is not very difficult to find large strong primes, for whatever usual definition of that 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 of prime order $q=(p-1)/2$.
About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find 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$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.
After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.
Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.
In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is seldom used, or perhaps is by accident. A better name is safe (RSA) prime.
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 primes less than some bound like 512-bit, or/and multiprime RSA, but only when when an adversary would be content with factoring extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).
Finding such safe RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. The basic idea is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.