(Personally) All-in-one plugin is the best, but Yoast SEO have a great advantage in the sitemap, which includes links and images. Can I disable everything in Yoast SEO except sitemap.? and make both plugins still installed.
I'd probably just keep the All-in-one plugin, which I agree feels better. Uninstall yoast, and download a plugin to specifically handle the sitemaps.
The good thing about Yoast over AllinOne is that it can no index your cat and tag archives where as Allinone doesnt give option to do that. The downside to Yoast sitemap is that the sitemap url has an underscore in it and underscore are not good for SEO! The upside to AllinOne is that you can use Google sitemap plugin with it where as you cannot use Google sitemap plugin with Yoast (causes inflictions).
Yoast moves many plugins, Robots.txt, Sitemap, etc all under one roof so you have less plugins active on your site. With All in One, you need those extra plugins active.