Currently it is still possible for an adversary to perform a replay attack during the short time frame covered by the timestamp validity period of signed requests. We can mitigate this risk by adding a unique ID to signed requests on the client side and storing that ID in a short-lived data structure in the backend, rejecting requests based on the ID value. Alternatively we can just hash the signed data and reject requests for signed data with the same hash.
Storage of these hashes can be very short-lived as we only need to retain them during the validity period of the given signed request.