How can transactions be verified without the private key?
Bitcoin transactions are not encrypted, they are cryptographically signed.

You can use a public/private keypair 2 ways:
(massive simplification warning)


Encrypt a message using a public key and then decrypt it with a private key
Sign a message using a private key and validate the signature with the public key


The second method is the one that is used by Bitcoin. A message is placed in the distributed ledger that bitcoins have been sent from X to Y (and typically Z), and signed by the private key of X. X is the source bitcoin address, Y is the destination, and Z is the change address.