Sayyidah Aishah Siddiqah (may Allah be pleased with her) reports this saying of the Prophet (peace and blessings be upon him): "Were it not that I feared putting my Ummah to hardship, I would have ordered them to use the tooth-stick (siwak) at every prayer."
Al-Bazzar recorded it. Its chain contains a narrator, Mu'awiyah bin Yahya al-Sadafi, who is da'if (weak).
Hadith Referenceمجمع الزوائد ومنبع الفوائد / كتاب الصلاة / 2548