The nonce is already used by the consumer with ID

Question

After Oauth handshake completes and the 4 Oauth values are generated I test an API call like this one:

curl --location 'https://[server name]/index.php/rest/V1/categories' \
--header 'Authorization: OAuth oauth_consumer_key="cxxxx",oauth_token="xxxx",oauth_signature_method="HMAC-SHA256",oauth_timestamp="1695063776",oauth_nonce="ibgFTWU7PrC",oauth_version="1.0",oauth_signature="L37dcwgYkiVRq6dBmZws6xMtm100KSTytXTb0OA5LqY%3D"' \
--header 'Cookie: PHPSESSID=g0obvg0d093llskg743pqmvebf' 

and response I get is:

{
    "message": "The nonce is already being used by the consumer with ID %1",
    "parameters": [
        "26"
    ]
}

Why is it telling me this and how could I overcome it?