Avoiding replay attack on certified announcements Suppose two agents A and B share a common secret and A makes a regular unique 16-byte announcement to B every 10mins which B must verify authenticity.

I'm thinking of letting the first 8 bytes be the message and the last 8 bytes be the HMAC(key, msg). The message itself contains an increasing counter, which B uses to reject all future messages with a lower counter. 

Given the uniqueness of each message and the strict monotonicity of the counter, should this scheme avoid replay attack?

Overall, is this a secure approach?

Thanks
[let] the last 8 bytes be the HMAC(key, msg)


64 bits is a pretty small tag size, and not considered "cryptographically strong".  I would suggest using the full HMAC output if possible, or see here for some discussion of reduced tag length.


  should this scheme avoid replay attack?


Assuming that the HMAC cannot be broken (which would imply that the key is kept secure and a sufficient tag size is used), this scheme looks fine against replay attacks.

(I suggest opening a new question with regard to your key derivation scheme)