The Messenger of Allah ﷺ said, "Were it not that I would impose hardship on my community, I would have commanded them to use the tooth-stick." Bukhari adds, "with every prayer," and Muslim's wording is, "at every prayer."
أن رسول الله ﷺ قال: لولا أن أشق على أمتي لأمرتهم بالسواك. زاد البخاري: مع كل صلاة، ولفظ مسلم: عند كل صلاة.
Malik narrated it in Purification (145) from Abu Zinad, from Araj, from Abu Hurairah, and mentioned it. Bukhari narrated it in Friday Prayer (887) through Malik, by this same chain. Muslim narrated it in Purification (252) through Sufyan, from Abu Zinad, by this same chain.