家を新築したいですが、私道問題で困っています。

まず、ご質問です。この「私道」は４ｍ以上の「２項道路」でしょうか？それとも土地の所有者の専有が認められる道路でしょうか？この認定が分からなければ、当該の建築事務所に問い合わせれば分かります。通常、袋こうじの土地に住む方の「通行権」は認めれらることが多いのですが、土地の件は、当該の役所、建築事務所が管理しているので、まずは、どのような性格の「私道」か問い合わせてみてください。

質問の趣旨から少々外れますが、この場合の私道が位置指定認定道路かどうかを調べる必要があるかもしれません。位置指定認定道路であれば、所有者の勝手な都合による変更廃止などは禁じられていますので、役所の道路管理課で調べれば分かります。

さて私道の使用料の件ですが、asutaroさんの敷地はいわゆる専門用語で言うところの袋地になりますが、これは隣地を通行に利用できる通行権が法律で認められています。

立て替えるまでその通行に利用している間の私道の使用料は文面から判断しますと徴収されていなかったのではないかと思われます。
通行料と言うものは必ず支払わなければならないということはありません。
支払わないといけないケースとしては、使用料を支払うという何らかの契約を締結している場合（建築知識200705P111より）であり、それ以外は支払う必要がありません。
したがって今回のケースでは、従前は支払っていなかったにもかかわらず建替えと言うことになって初めて請求されたということであるならば、支払いの義務は無いものと思われます。

近隣の方も支払われているということは、ご近所とのトラブルを避けたいという気持ちがあったのかもしれませんが、民法に絡みますので対処方法はお近くの弁護士事務所に相談されて見たらいかがでしょうか。

建替えのご質問ですから新築工事と言う事で回答させていただきます。

建替えに当たって行政に建築確認申請が必要ですが、確認が済んで工事
に掛かる段階でしょうか？そうだとするとatsutaroさんの敷地が道路に
接している状況が図面に記載されていますので確認をして下さい。
ご質問を読ませて頂きますとatsutaroさんの敷地は隣家所有の道路状の
敷地に接していましがその道路状の敷地の扱いが不明ですので私道使用
料の正当性は判りません。
4ｍに満たない道路状敷地で確認が済んでいるとすれば建築基準法第42条
の2項道路の扱いの可能性が高いです。建築基準法第42条1項5号（位置指
定道路）の場合は現状復帰（位置指定を受けた際の道路幅員）が求められ
ますので確認通知書を見れば判ります。

以上が合法的な手続きによる建替えですがその場合には隣家所有の敷地を
借りて確認申請を行っているわけですから使用料を払うのは当然の事と言
えます。そしてその敷地に水道の本館を引き込んだ費用は隣家が負担した
と考えられますのでその事を考えての応分負担の意味が有るとも考えられ
ます。

???共に敷地の状況により変わりますので相場と言う物は無いと考えて
下さい。

隣家に印鑑を求める段階であれば、家の設計は済んでいると思いますので
設計した建築家に相談するのが一番確実です。atsutaroさんが疑問に思っ
ている事が早く解消できると思います。