Migrating from 0.11.5 to 0.12.6. How to extract key-id from JWS in order to parse it?

[YaShargano]

Hi! I'm migrating from 0.11.5 to 0.12.6 and I've got a little problem :)
In short - I have a service that authorize users. The service is running in multiple instances, for examples below let's assume there are two instances A and B. Each instance is signing JWT with it's own private key (private keys A and B respectively). When signing a JWT service also put a kid header with the ID of key. Public keys and their IDs are stored in some cache (let's say Redis).

So, I've got situation on instance B when I need to verify token signed by instance A.
Previously (on 0.11.5) we first parsed data from token (including kid) and then we verified token by the Public key fetched from cache by this kid.

Currently (on 0.12.6), during migration, I faced out a problem - I couldn't parse headers without verifying the token, cause there is alg header present. I'm getting exception saying:

Cannot verify JWS signature: unable to locate signature verification key for JWS with header: {kid=my-very-awesome-key-id, alg=RS512}

The problem is that I need to parse token and extract kid first, but it's not possible cause I already need a key. Kinda cyclic dependency.

Code for JWS building:

var token = Jwts
      .builder()
      .header()
      .keyId("my-very-awesome-key-id")
      .and()
      .expiration(tomorrow)
      .claim("user-id", userId)
      .signWith(privateKey, Jwts.SIG.RS512)
      .compact()

Parser code (not working, throwing an exception):

Jwts.parser().build().parseUnsecuredClaims(token)

P.S. using unsecured for ParserBuilder also doesn't work, cause the alg header isn't none or missed, it's present.