How to Compress Files Quickly and Efficiently?

It depends on what you want to compress.

If the video file in question is already in a compressed format, there's probably nothing more you can do short of re-encoding it at a lower data rate (reducing video resolution or reducing the audio kbps rate). Again, you mentioned that re-encoding is too slow, so probably not an option.

Compression algorithms rely heavily on repetitive sequences in data. A common scheme involves building a dictionary to shorten repetitive sequences.

For example, consider the string "eabcdabcdabcd".

That can be compressed by setting a dictionary rule "f = abcd", then representing the string as "efff".

Now consider the string "abcdefghijkl".

There are no repeated sequences, so it's impossible to compress with a dictionary approach.

Compressed file formats already have much repetition removed; therefore compressing them further probably won't produce further benefits. In some cases, compressing a compressed file can increase its size (a well-known phenomenon with ZIP format).

Compressing images and video is "more complicated" then compressing for example text files because regular compression methods like zip etc. won't give you a very good result as you noticed yourself (user1258361's comment gives you a bit of insight here).

I would suggest to reduce the resolution, this is simple and will give you a significant reduction in size but on the downside it will reduce the quality of the pictures and videos. There are various tools for reducing the resolution via a CLI (command line interface) and this question has been asked many times, e.g. this one for images. Just start a search and give it a try, if you run into specific problems you can ask a(nother) question. Note: depending on your HW this might not be very fast though (but neither are "good" compression algorithms, the more compression the more computation has to take place - in layman's terms).

Compressing without (significant) loss in quality is more complicated because choosing the compression method depends on the content of the image/video in regards to your requirements to quality. You will need to re-encode your files with a different compression format. There are a few lossless compressions but they probable won't give you sufficient results. To my knowledge there is no general answer here.

PS. Software suggestions are out of scope here on superuser.