It is not very difficult to find large strong primes, for whatever usual definition of that is used.
___
The standard definition of [strong prime][1] (OEIS [A005385][2]) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called [Sophie Germain primes][3] (OEIS [A005384][4]).

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][5] 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][6] to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a [Rabin-Miller test][7] for $q$. It is not necessary to further test $p$: by [Pocklington's theorem][8], 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][9] 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][10] 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][11] factoring),
 - and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the [cycling attack][12]).

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

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

  [1]: https://en.wikipedia.org/wiki/Safe_prime
  [2]: https://oeis.org/A005385
  [3]: https://en.wikipedia.org/wiki/Sophie_Germain_prime
  [4]: https://oeis.org/A005384
  [5]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve
  [6]: https://en.wikipedia.org/wiki/Euler%27s_criterion
  [7]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  [8]: https://en.wikipedia.org/wiki/Pocklington_primality_test#Pocklington_criterion
  [9]: https://en.wikipedia.org/wiki/Strong_pseudoprime
  [10]: https://people.csail.mit.edu/rivest/Rsapaper.pdf
  [11]: https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
  [12]: https://crypto.stackexchange.com/questions/1572/cycle-attack-on-rsa
  [13]: https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm
  [14]: https://people.csail.mit.edu/rivest/RivestSilverman-AreStrongPrimesNeededForRSA.pdf#page=7
  [15]: https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf#page=60
  [16]: https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
  [17]: https://en.wikipedia.org/wiki/General_number_field_sieve
  [18]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem