There are many ways to skin a cat, but for your context I suggest the following.
First, authenticate the servers with TLS/SSL. Obviously, this only authenticates the server, not the client; so, to authorise a request, the server should contact what it expects be the origin server and seek confirmation.
API Request Authorisation
The exchange would look like this:
Client Server B Server A
| ----- data -----> | |
| | --- validate ---> |
| | <------ ok ------ |
| <--- response --- |
- An unauthenticated client makes an API call to a server authenticated via SSL/TLS, the request contains an auth token.
- The receiving server takes the auth token and contacts what should be the server that generated the request and asks whether it generated the auth token. This origin server has now also been authenticated via SSL/TLS.
- Depending upon whether the auth token was validated, the API request can be approved/denied.
- Client -> Server B: "Do X, Y, Z. Auth:abdhs67ruhbf"
- Server B -> Server A: "Did you send me a request with Auth:abdhs67ruhbf"
- Server A -> Server B: "Yes."
- Server B -> Client: "Result: A, B, C."
This obviously has a high latency cost if the servers are far away from one another.
As User949300 suggests, it would be advisable to place an expiration time on auth codes when they are generated (e.g. 24-hour TTL) so that attackers don't try to exploit old tokens.
For the same reason, when the response to an API call is received, the token used to make the call should be revoked.