JWT Common Practices
How should verification work? - JWT documentation are your friend.
Should I look at the JWT's signature section and verify with the private key each time? - https://scotch.io/tutorials/the-anatomy-of-a-json-web-token
should I store the token in a No-SQL? - NO, there's no need if you are able to decode the token that mean the token is valid.
secret key be? it's depends the bigger the key the slower your api so its a trade off (remember you need to decode the token on every request)
Is RSA with the HMAC SHA256...? Most people using HS256,


I'm recommending for you to check out this url 

Hope it helps,