How should I construct a random challenge for challenge-response authentication?

I am reviewing the implementation of a cryptographic challenge-response protocol. The password is used as the key to encrypt a cryptographic nonce (the challenge), and the result is compared with the response.

Currently, the nonce is not really secure as it is obtained with srand() and rand(). All of the ingredients of the random number seed (the current time in seconds (!) and the pid) are quite easy to guess for a man in the middle. This is obviously not good but my question is, how bad is this at preventing replay attacks? Should the challenge be obtained from a CSPRNG (such as /dev/urandom)? Does anybody have any pointers to best practices?