Problems with deterministic ECDSA based on RFC6979 in Bitcoin Generating random number k in elliptic curve is crucial and in any transactions signature in Bitcoin, random number k is required to compute a point k*G. If this k is chosen not randomly, it instantly leaks the private key.  
Therefore, they came up with an idea of deterministic generation of ECDSA which is described in RFC6979. Basically they concatenate the private key with the hashed message and use an HMAC function and generate a pseudo random k. 
This method seems simple and easy. 


Does it introduce any overhead?
If yes, is this overhead negligible?


Or generally is there any inefficiencies or problem with this method and why do we still see non-deterministic implementation of ECDSA?
Not any serious efficiency concerns. Signing is done fairly infrequently for any particular client (only a few signatures per transaction usually). While possible that the signing might take slightly longer to generate the k value, it would not be noticeable, especially considering how infrequently it is used by any one particular client. It's the verification of all the signatures that is the CPU bottleneck for block verification in bitcoin, because all full nodes have to verify the signatures of all the transactions on the network, and this takes the same time regardless of how the k parameter was chosen. 

Gregory Maxwell made a comment about the use of deterministic k values here:


  The primary arguments in most spaces against derandomizing DSA are
  FIPS conformance (irrelevant for us) and reasonable concerns about the
  risks of using a (less) reviewed cryptographic construct. With
  widespread motion towards derandomized DSA this latter concern is less
  of an issue.


The new libsecp256k1 library by Pieter Wuille actually uses deterministic generation of k.

Also note that one of the key benefits of using this construction is that you need not worry about a weakness in your PRNG being exploited in the signing process. For example, signing different pieces of data with the same k value instantly leaks your private key. A similar attack can also be exploited if the PRNG is weak enough to determine the relationship between different k values used when signing the same piece of data. Since the k is deterministically generated from the data you are signing (and the private key), these concerns about the PRNG are no longer as relevant, as you will always produce the same signature for the same piece of data. This also makes writing ECDSA unit tests easier.