Not much point in upgrading from 2048 bit RSA to 4096 bit RSA. Instead, you should plan to upgrade to ed25519 keys when your client and servers support them - faster and better security than RSA.
Of course that is an "if" one should carefully think about -- e.g. it is OK if all you are using is OpenSSH at version 6.5 or later. (That can be a problem with many older boxes). But other than that, last I checked only SSH.NET and tinyssh supported ed25519 keys. Shameless plug for some more data on this: http://ssh-comparison.quendi.de/comparison.html (yeah, that page could be a lot better -- pull requests are welcome)
If you have experience with RSA key pairs, using ed25519 key pairs is easy. To generate a key pair just run: ssh-keygen -t ed25519
As with RSA, this command generates a public and private key file. Put the public key in the authorized_keys file on the server side.
You'll need OpenSSH 6.4 on both the server and the client side. If you have an older version, I would not recommend upgrading outside of your operating system's normal upgrade channel because then you'll be responsible for security updates. Instead I would wait until your operating system has it.