The private key is unrelated to the passphrase. So is the public key. The public key is also generally stored unencrypted, even when the private key is protected by a passphrase. (Exceptions may exist where the public key is stored in an encrypted form, but in the basic case and assuming a sufficiently large key, doing so provides no additional security because the public key is meant to be publicly distributed or at least can be assumed to be available to an adversary.)
Now, don't get me wrong. Protecting your private key with a passphrase is a very good idea, and it is best practice to do so. The private key and the public key have a mathematical relationship to each other. But your private key is still just a number. This number is unrelated to the passphrase you use to encrypt the file that holds this number, which is all the passphrase does.
If an attacker Eve knows the passphrase in addition to the Public Key; Can they derive the Private key? - I presume yes with enough time.
The public key is mathematically related to the private key, and the simple answer is that yes, with sufficient time, in theory, one can be derived from the other. The public key almost by definition needs to be transmitted in the clear in order to establish an identity before the encrypted communications channel is set up, so Eve (by convention Eve is a passive eavesdropper; Mallory is an active man in the middle) can see it.
Deriving the public key from the private key in RSA is easy. Deriving the private key from the public key is supposed to be computationally infeasible, and with sufficiently large keys effectively impossible. So far as we know, there is no fast way to derive the private RSA key data from a 4096-bit public RSA modulus on a classical computer (which is what we currently have). Even an efficient attack on a 2048-bit public RSA modulus would be quite a feat, though 1024-bit RSA is within the realm of possible in reasonable amounts of time and a 768-bit RSA private key has been factored in public (it took the equivalent of on the order of 2,000 CPU-years on reasonably modern hardware).
So, "with enough time", it is possible. But that is unrelated to the passphrase, or lack of passphrase.
To understand the why of the above, I will use textbook RSA for simplicity. (Real-world RSA is similar to, but not exactly the same, as textbook RSA, as there are many real-world attacks that textbook RSA doesn't deal with.) Here, among some other numbers, the private key is the pair of prime numbers commonly referred to as p and q, and the public key is their product, n=pq, where n is referred to as the public modulus. Given p and q, calculating n is borderline trivial (you just need to multiply two -- very large -- numbers together), but given only n, determining the corresponding values for p and q is extremely difficult. We have no proof that this is so, though; only the absence of any publicly known easy way to actually do it, even with lots of very smart people having worked at the problem for a long time. It's like figuring out that 15 = 3 * 5, except that instead of numbers of a few digits, the numbers involved are many hundreds of digits. To a first order approximation, with your 4096-bit RSA key, n is about 1300 decimal digits long, and p and q are about 600-700 decimal digits long each.
If they can derive the public key, what algorithms can they use to do this? - I don't know.
Semiprime number factorization algorithms. The current state of the art for numbers larger than 10^100 (100 decimal digits, about 332 bits) is the General Number Field Sieve (GNFS) algorithm.
A quantum computer could use Shor's algorithm to efficiently factor a semiprime, but (at least in public) we don't yet know how to build a large enough quantum computer that actually works. That's part of what the push toward so-called post-quantum cryptography is about. Last I heard, state of the art was having factored the number 15, but that was a few years ago; it is possible that publicly known quantum computers are now able to factor numbers larger than 15.
What is the number (or order) of operations needed for each algorithm to derive the Private key?
The complexity of factoring a number using the GNFS is discussed on its Wikipedia page. It's really difficult to discuss the number of operations directly, but after some discussion on prerequisites, the Wikipedia article summarizes by stating that the running time of the number field sieve is super-polynomial but sub-exponential in the size of the input. You can compare the various factoring times and algorithms used for the various RSA numbers, which were part of a competition started in the early 1990s to expand the knowledge relating to integer factorization, now inactive.
Compare also How is it possible that people observing an HTTPS connection being established wouldn't know how to decrypt it? Note that HTTPS works differently from SSH, but the basic operating principle remains similar.