Welcome to the club.
I have an Epiphone Les Paul that had the same issues. I bought a Nashville Tune-o-matic bridge and had it sent to the local lutheir to have it slotted, or whatever it is called, and properly set up and it's been awesome ever since. i think all in it ran me around 150 bucks. For bridge and Luthier.
If it is one of the cheaper epi's you may not want to put another 150 bucks into it so i would suggest taking it local music store that will do a proper string chnage /set up on it for you and you may find that will make a huge difference. Cheap Epi's can be really misleading and crap shoot. 50% of them are great little guitars. the other 50% are night mares.