So suppose you are doing this locally (so no network noise), and know the exact specifics of your processor too.
Ok. This is a plausible attack model, for example, if the attacker is running a JavaScript ad in your browser, or has a co-located virtual machine on the same cloud.
Is it feasible to figure out the private key (while having access to the public-key) generated by libsodium based on the time it takes to generate a key-pair?
Libsodium uses Curve25519 elliptic curve keys. A Curve25519 private key is a random bit-string of a certain lengths. (It's expanded to a byte string where certain bits have fixed values, but that doesn't add a timing side channel.) So the private key generation process is trivial. The only plausible side channel is in the random generator itself.
Some random generation algorithms use primitives that are susceptible to timing side channels. In particular CTR_DRBG relies on AES which is vulnerable to cache timing attacks if implemented in software in the naive fast way. CTR_DRBG rotates the AES key very often, which makes it somewhat less vulnerable than in scenarios where the adversary can observe encryptions with the same AES key. However, such an attack can be practical, at least in ideal conditions.
With other popular DRBG algorithms (e.g. Hash_DRBG or HMAC_DRBG), with a non-table based AES implementation (e.g. using hardware acceleration such as AES-NI, or using bit-slicing in software), or if the DRBG reads entropy often enough (which is feasible on modern hardware with a dedicated TRNG, such as RDRAND on Intel processors or the equivalent on various smartphone processors), timing attacks on the RNG aren't a concern.
What could be more vulnerable is the calculation of the public key from the private key. Curve25519 makes it relatively easy to implement arithmetic without timing side channels, but it isn't a given.
What about other algorithms, how feasible is this in general?
With Weierstrass elliptic curves, and with finite-field Diffie-Hellman, a private key is a number between $2$ and $P-2$. Aside from RNG attacks as discussed earlier, the natural implementation of the key generation process is not susceptible to timing attacks. However, the calculation of the public key is vulnerable to timing attacks if implemented without precautions.
With RSA, key generation is a complex process involving (pseudo-)primality testing and some additional arithmetic that is potentially vulnerable to timing attacks. Specifically, in practice, it seems that the step that is most prone to leakage is the GCD calculation done to check that $p-1$ and $q-1$ are co-prime with the public exponent.
