My Friend and I have been generating a few ssh2-rsa keys and noticed that all the public keys began with "AAAAB3NzaC1yc". The similarity extended to "AAAAB3NzaC1yc2EAAAABIwAAAQEA" between two keys I generated on the same machine on two successive attempts. I can even google "AAAAB3Nz" and end up getting a few hits.
Is this normal? Or are we doing something wrong while generating? Suffering from insufficient randomness?