
大前提として、その男性が子どもたちを認知していることが必要になります。もし、認知がまだなら、任意認知を求め、拒否するようなら家庭裁判所での認知調停、認知訴訟と進むことになります。
認知済み、あるいは任意認知に応じるとなれば、公正証書の作成は可能ですし、公正証書を残すことが望ましいです。口約束や当事者同士だけで作成した書面だと、未払いになった際にすぐに強制執行(口座や給与の差押)ができませんので。
もし、認知成立後、相手が養育費の支払いに応じないなら、やはり家庭裁判所で養育費の調停・審判をおこなうことになります。
公正証書では、月ごとの養育費の金額、始期と終期(いつから支払が始まり、いつ終わるのか)、特別費用について(例えば私立大学に進学する場合の学費の扱いなど)等を決めるのが一般的です。