Should all GPG keys begin with 0x?
I've created a GPG key on a newly installed Debian virtual machine. I've noticed that most keys I've seen begin with 0x, however the one I created doesn't. I selected 'RSA (set your own capabilities)' with a 4096 bit key size. Should I create again this key?
most keys I've seen begin with 0x
I assume you are referring to the Key ID, and the 0x is not part of the actual key ID, but merely a display option indicating that the string of digits are hexadecimal (which all Key ID's are, including yours, regardless of whether they are prepended with "0x").
Should I create again this key?
No. The key is fine.
If you want GnuPG to display your keys with the "0x" you can add the option
keyid-format 0xlongto your gpg.conf file.
If the gpg.conf file is not already present in your home directory's .gnupg/ directory, you can create it with bash:
echo 'keyid-format 0xlong' > $HOME/.gnupg/gpg.conf