It is not very difficult to find large strong primes.
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 an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).
Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method 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.