Is it insecure to make nonce using random number generator and hashing algorythm with secret key like HMAC?

I'm building a project on Arduino Mega microcontroller and I need some nonce generator for challenge-response exchange. But I failed to find some alphanumerical string generators. Then I came up with an idea to make one using the random() function that generates random int in limit you give and hash that integer with HMAC using another secret key (one that could be auto-generated on startup since it doesn't need to be consistent).

Does this approach make my nonce less secure in some way?

random() is rubbish. See some of the source here.

The best way to generate nonces is via a true random number generator, unless you want >10,000 nonces per second which is unlikely in a microcontroller situation. You can do that without any additional hardware using the Arduino Entropy Library. The library utilises the natural jitter between the AVR's clock and the watchdog timer. This is a well researched area of TRNG design commonly used in ring oscillators. Or roll your own variant (it's not that hard if you review the original code).

It's not very fast, (64 bits/s) but it will give you a truly random 96 bit nonce in less than two seconds. That way you don't need to keep track of used nonces. And it's reboot proof.

The approach you use depends on the requirements of the nonce. In the case you describe, a challenge-response protocol, the requirements of the nonce are usually that it's unique and never reused. However, there are other situations where the nonce needs to be unpredictable as well, such as if you're using CBC mode for encryption.

You can use HMAC with this and for a hash function to use with it I'd recommend SHA-256. However, I would not recommend generating the value to HMAC using random because that might repeat and then so would your nonce. In general, you cannot rely on the quality of the PRNGs in standard C and POSIX. You could use a monotonically increasing counter instead, which would ensure that it never repeats, but you would have to have some way to persist the counter between uses.