Why does SSH authentication protocol send a challenge message instead of using digital signature to verify client Why does SSH authentication protocol choose to have the server with the public key send a challenge message encrypted with this public key of the client instead of having the client send a message signed with it's private key along with client ID and have the server verify the signature?

Wouldn't verifying the signature be enough proof that the client really does possess the private key and hence is authenticated?
The server sending an encrypted challenge has a few advantages over the signature-based method you described:
1) It is more efficient for the client in the case that authentication is rejected outright.
If the server doesn't recognize the client's public key, there's no reason to have the client waste time and energy generating a signature.
2) It is more secure from the server's perspective since the challenge is, for all intents and purposes, completely unique per connection.
The server is not just trying to verify that the person who signed the message has the private key but that the client it is connected to is the one who signed the message.  So a signature would need to be of data that could not have been stolen from a separate communication (either with this server or another one).
3) It also helps protect the client's private key from clever attacks.
As described in section 3.4.2.2 of the O'Reilly book on SSH:

The client receives the challenge and decrypts it with the corresponding private key. It then combines the challenge with the session identifier, hashes the result with MD5, and returns the hash value to the server as its response to the challenge. The session identifier is mixed in to bind the authenticator to the current session, protecting against replay attacks taking advantage of weak or compromised random-number generation in creating the challenge.
The hashing operation is there to prevent misuse of the client's private key via the protocol, including a chosen-plaintext attack. If the client simply returns the decrypted challenge instead, a corrupt server can present any data encrypted with the client's public key, and the unsuspecting client dutifully decrypts and returns it. It might be the data-encryption key for an enciphered email message the attacker intercepted. Also, remember that with RSA, &quot;decrypting&quot; some data with the private key is actually the same operation as &quot;signing&quot; it. So the server can supply chosen, unencrypted data to the client as a &quot;challenge,&quot; to be signed with the client's private key -- perhaps a document saying, &quot;OWAH TAGU SIAM&quot; or something even more nefarious.

4) A signature based method, implemented properly, would still require the same number of steps, due to the logic in (2).
That is, because the server wants to be sure that it the client has the private key, even in a signature based method it would be best for the server to send a random challenge and have that signed, making the process look very similar but without the benefits described above.