I've always seen this delay; VERY ANNOYING. Hard to believe the SSO handshakes take this long. I'm sure you could write a business rule to execute on Selection of vRA Catalog Item that would kick off the authentication. Sorry not a ServiceNow developer or I'd give you more details. We worked around this by removing everyone from vra_users and utilized a single service account. All entitlements/requests go through as a single service account. If you need to change ownership of the VM at the end, use vCO.
@GigaDuck - We already gone through this and as per serviceNow Login rule deprecated but not obsolete.
We had a POC where we implemented login redirection some other way but it had some limitations wrt Customers existing modules on ServiceNow platform so dropped that idea as it was not unique across all customers.
We will let you know once any other workaround is implemented in this case.