Using public-key signature instead of having API key
Using public key cryptography instead of a long-term shared secret is slightly more complicated but has major advantages. One of them being that the server doesn't learn the secret key. This protects against accidental leaks, but also insider threats.

If this is an option, you can use client TLS certificates. Most HTTP client libraries support this, but web server often have limited support for this. Namely, they support ACLs based on the presence (or not) of a certificate, but that's pretty much all they do. And it's not always possible to retrieve client information from web applications.

The scheme you describe (the server sends something that the client has to sign) works. However, you shouldn't use a time stamp, which would be vulnerable to replay attacks, but a nonce.