It is not very difficult to find large strong primes.
___
The [original RSA article][1] 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][2] factoring),
 - and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the [cycling attack][3]).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against [Williams's p+1][4] factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's [_Are Strong Primes Needed for RSA?_][5]).

Modern practice (in particular,  [FIPS 186-4][6]) 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][7], [GNFS][8]..). 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][9], and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.


  [1]: https://people.csail.mit.edu/rivest/Rsapaper.pdf
  [2]: https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
  [3]: https://crypto.stackexchange.com/questions/1572/cycle-attack-on-rsa
  [4]: https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm
  [5]: https://people.csail.mit.edu/rivest/RivestSilverman-AreStrongPrimesNeededForRSA.pdf#page=7
  [6]: https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf#page=60
  [7]: https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
  [8]: https://en.wikipedia.org/wiki/General_number_field_sieve
  [9]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem