Definately remove the old thermal paste first. As must as you might wanna save them they are no long good. As they may be cheap material and/or they will no long be evenly spread once new paste is applied. That said you're prong to have heating issue with cpu.
I don't know the kind of your cpu you ahve but if it is your first time use caution especially with the old cpu models ones with pins on them. They will break and only can be repair with needle nose plier once or twice. with new once they just plug in like any hardware card. Just watch out for the right corner. Mine is marked with a triangle witch for my board goes toward lower right corner. Looking your user manual your may be different marking or notification.
I went a little more than you asked but I hope this helps you resolving your issue.
remove the older thermal paste with an alcohol solution and cloth.
while your case is open get some compressed air and blow out your case as well.
there are different ways to apply and some say it depends on your processor which is best.
I just use a spread technique and cover most of chip before I re-place heatsink.
I also use AS5 and I stand by it or look for something better in quality but definitely nothing less.
I agree. I use a similar technique and stand by Arctic Silver 5 as well.