A computing device may include a memory and a processor cooperating with the memory and configured to receive a connection request from a client device having a public/private encryption key pair associated therewith. The connection request may be based upon a connection lease and the public key for the client device, and the connection lease may be generated based upon an authenticated version of the public key for the client device. The processor may also be configured to verify that the authenticated version of the public key upon which the connection lease was generated matches the public key for the client device and authorize a connection with the client device and provide the client device with access to a virtual computing session via the connection.