How can I increase the frame size of the titles in Adobe Premiere?
As far as I know, unfortunately you can't take an old title which was based on whatever frame size, and switch its size to something else. The only way I know for your situation with the small titles is:


Double click on a title that you want to change (either on the timeline or in the project).
In the title editor window, click on the top left button of 'New title based on current title'.





A pop up shows - type in the size you want for the NEW title AND don't forget to check (or change) the name of that new title, just that later on you know which title is which. Click OK.
You have just created a new title, you can find it in your project. It has the old text with all its preferences, inside a new size frame; the visual result is the same as you would have got with scaling, but w/o the quality loss.
That should do the trick for you, but you'll still have to do it one by one on all the titles, and then to put each one in the appropriate place on the timeline. 


I hope that helps. Good luck!