The MAC is the right tool here, and HMAC/SHA-256 is fine. Using a 5-second tolerance might be a bit optimistic:
You have to make sure that both servers have accurate clocks; use NTP. Also, make sure that you use a well-defined representation, i.e. something in UTC (otherwise, you'll run into trouble with Daylight Saving Time).
The "5-second delay" must be enough to accommodate the round trip: server A sends the "redirect" response to the client, then the client connects to B and sends the request. If the client is in adverse conditions (e.g. a client using a laptop in a train), network can be unavailable for a few seconds at a time.
Replay attacks from outsiders are prevented by SSL; the inclusion of the time stamp is to defeat replay attacks by the user himself. If server B requires a time stamp no older than n seconds, then this implies that if you block access to the user on A, then the user may still talk to B for n seconds. You can probably tolerate a longer n; personally, I'd use a 5 minutes delay. Another way to look at it is the following: if, once authentication was performed, B allows successive requests within a given time frame T, e.g. with a cookie-based session management and the session expires after T seconds, then it makes relatively little sense to use a n much shorter than T.
Note that an evil user may want to fake NTP packets in order to make server B's clock go back to the past, in order to reuse an old authentication URL with a long-expired MAC. NTP packets are not authenticated. A normal NTP client will not accept to alter its clock by considerable amounts even if a NTP server claims that it is off by several weeks; however, a boot-time ntpdate call may be theoretically abused. I have not observed this attack in practice.
Suggestions for improvements:
You may want to include an identifiers for A and B (e.g. server names) in the redirect URL, and as part of the MAC input. This keeps track of who is doing the authentication+authorization, and for what server the user is authorized. This is more flexible if you want to later expand the system with several distinct A and B servers.
You can replace the MAC by a digital signature (RSA, DSA...): server A owns the private key and uses it to sign; server B uses A's public key to verify signatures. This avoids sharing a secret between A and B (the more a secret is shared, the less secret it becomes).
