Efficiently show/prove knowledge of third party secret without leaking information
Public-key cryptography is not sufficiently computationally burdensome to where other approaches must be used for authentication protocols. Note though that what you describe is not actually public-key based. The verification of the MAC requires Dave and Bob to both have a shared key. Also, note that a random component must be included in some manner in all authentication protocols, else an attacker will be able to mount a man-in-the-middle attack and/or reuse the authentication string in the future. However, similar schemes that are based purely on public-key algorithms do exist, and are more commonly used. Either way, Alice is acting as a $TA$, verifying Bob's identity through some secondary channel and publishing a mechanism by which Dave can confirm that the owner of Bob's private signature algorithm (presumably Bob) is in fact Bob. 

In this case, the computationally burdensome process, generating public-private key pairs, occurs not every time authentication takes place, but only when Bob asks Alice for a certificate. Also note that generating public-private key pairs is not particularly expensive, provided access to either an efficient cryptographically secure random number generator or a large pool of entropy, both of which are relatively easy to have. 

Beyond that, public-key algorithms are designed so that the encryption and decryption processes can be computed efficiently. For instance, RSA and other Discrete Logarithm based problems have square-and-multiply or some variant. As such, the actual signing and verification step for Bob and Dave is quite simple and efficient, and there are a number of schemes which require only the limited computing power of say, smart cards.