I am having urls displayed with category and article ids such as http://www.mysite.com/54-mycategory/59-myarticle. In order to remove the numbers, I had to manually create menu items for each article - which then successfully omits the numbers from the urls.
This is perhaps not the right way to create SEF urls as this requires extra work to create the menu items. Does anyone know of a better way to do this? I couldn't find any extensions that can do this effectively.
No, this is how Joomla default routing works in both 2.5 and 3.x versions.
You need to either create a menu item per each article, as you did, or install a 3rd party plugin to handle it.
In your case I guess that most SEF extensions in the Joomla Extension Directory will do. I had good experiences with SH404SEF (a very complete solution) and Simple Custom Router (a very basic plugin - intended for coders)