What’s the best approach for generating a new API key?

Use a random number generator designed for cryptography. Then base-64 encode the number.

This is a C# example:

var key = new byte[32];
using (var generator = RandomNumberGenerator.Create())
    generator.GetBytes(key);
string apiKey = Convert.ToBase64String(key);