No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications.
You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private keys must be related, but not in an obvious way. What means that whatever scheme is used has some mathematical structure. Number theory is a place where we find 'related-but-not-in-an-obvious-way' mathematical structures, and primes are rather, err, primary in number theory.
Exactly how the primes are used depends on which asymmetric algorithm is used; in RSA, we exploit the fact that, given $M^e \mod N$ (and $e$ and $N$), there's no known way to recover $M$ without knowing the prime factors of $N$ (but with that information, it's easy). In DH/DSS, we exploit the fact that, given $G^x \mod p$ (and $G$ and $p$), there's no known way to recover $x$ (and we have $p$ be a prime because the problem with composite moduli becomes a lot easier if someone finds the factorization). In Elliptic Curve Cryptography, we exploit the difficulty of recovery $k$ given $kG$ (where $G$ is a known point); a prime is involved because Elliptic Curves are defined only a field, and the only finite fields (that is, fields with a bounded set of elements) have size $p^N$, for prime $p$ (and positive integer $N$).
Now, you occasionally see primes used in symmetric crypto; it's not nearly as common (and those primes aren't secret).