Deploying over FTP takes ages

Is it normal that uploading the entire Grav install (8000+ files) takes really really long?
Shouldn't it take just a few minutes?

And do I need to copy over the "cache" folder?

And also, what's the best way to upload new changes made to my local version? It's pretty tedious to keep track of all changed files and then FTP them manually...

For the initial upload it's best to do it as a zip I would say. Transferring lots of tiny files always takes a long time, one big file is larger but much more efficient. I personally use GitSync to manage changes to pages, and I have my theme checked into Git too - though I don't use GitSync for that.

What @RosemaryOrchard says is true, transferring a binary file is much faster than the individual files. Further, once you have installed Grav on your server there is no need to transfer anything other than what is in your /user-folder. In general, you can upload the entire /user-folder without worry, or just specific parts of it if you prefer -- like /user/pages.

When you wish to upgrade Grav itself, manually, you need to upload all files - but that is quicker if you use the Admin-plugin.

Download the zip directly onto the server with wget or something if you can. Otherwise, upload it all. For some reason, FTP is very slow with many files.

I don't use the GitSync plugin, but I do have most of the user folder in Git in a remote repository. So when I develop locally, I push to the remote repo (on Bitbucket), then I can pull into the server. This is much quicker, more reliable, and simpler. I could automate more, but that process is fine for me right now :)