公正証書遺言があるのですが、半年以上話が進んでいません。

さぞご心配のことでしょう。

時間がかかることで費用が嵩むということはありませんが、相続手続の中には早くしないといけないものがあります。
早くしないと税制上の優遇を受けられなかったり、役所での保存期間がすぎて書類を取得できないなどということにもなりかねません。

遺言執行者が辞任をした場合は、裁判所にあらたな遺言執行者を選任する申立を行う必要がありますが、何の報告もなく半年も経過するというのは心配ですね。
弁護士費用についても心配されているのであれば、見積書の提示を受ける・費用の算定方法について説明を受けるなどしたほうがよいと思われます。

また、すでにその弁護士さんを信頼するのが難しいようでしたら、「これ以上時間がかかるようであれば他の専門家に頼みます」とおっしゃってみてはいかがでしょうか。

解任の手続を違う弁護士に依頼されたとのことですので、その弁護士に期間や費用の点について説明を求めるべきと存じます。

遺言執行者の辞任または解任は、いずれも家庭裁判所の許可を要する事項であり、遺言執行者が自ら辞任許可の申立をするか、相続人等の利害関係人が解任申立を行う必要があります。本件では遺言執行者が辞任許可申立を行っているかどうかを確認し、未了であるならば利害関係人として遺言執行者の解任申立を行うべきかと考えます。この場合、解任の正当理由の存否が審理の対象になりますが、遺言執行者自身がが辞任の意向を示しており、解任に抵抗しないのであれば、審理にはさほど時間はかからないのではないかと思われます。二人目の弁護士費用に関しては、報酬契約書は取り交わされていないのでしょうか?本来、弁護士は受任に際し、報酬に関する説明を行い、報酬契約書を作成する義務があります。もし、これが未了であるならば、報酬についての説明を求め、きちんとした報酬契約書を取り交わすべきだと考えます。

1.遺言執行者たる最初の弁護士との連絡が取れるようになったのでしたら、現在依頼されている弁護士を通じて、預かり書類の返却や相続財産の管理をしている場合はそれらの返却を請求されてはいかがでしょうか。遺言執行者に対する業務懈怠等、責任の追及については、現在の弁護士とよく相談なされてお決めになるとよいでしょう。
2.新たな遺言執行者の選任申立手続と現在の遺言執行者(最初の弁護士)の解任請求申立手続は、いずれも管轄の家庭裁判所にて行う必要があります。管轄裁判所の事務処理状況にもよりますが、通常遺言執行者の選任申立てには、約1ヶ月程度です。ただし、本件では遺言執行者の解任請求手続と一体の手続とみなされる可能性もあります。解任請求申立手続は、現在の遺言執行者の弁護士が、解任の是非を争えば、数か月以上かかることも考えられます。
※仮に、遺言執行者の選任申立手続が先行されて、現在の遺言執行者が辞任・解任される以前に新たな遺言執行者を選任してもらうことができたとしても、現在の遺言執行者を無視して遺言執行を進めることは困難であると思われます。なぜならば、民法上、相続財産の保存行為を除く遺言執行業務については過半数制度が採用されているからです。本件で、現在の遺言執行者に加え、新たに遺言執行者1名が選任されたとしても、その2名が承諾しなければ遺言執行することができないことになってしまい
ます。
3.遺言執行者の報酬は、公正証書遺言書に報酬算定の基準が定められていれば、その定めを基準・目安とすることができますが、本件のように遺言執行者の任務懈怠責任の問題が生じている状況では、報酬の支払の要否を含め、現在依頼されている弁護士とよく相談されるのがよいと思われます。遺言執行者がこれまで行った遺言執行事務についての報酬支払をめぐって、預り書類等のスムーズな返却、引継ぎが阻害される要因になりかねないからです。公正証書に報酬の定めがなければ、管轄家庭裁判所に対して、遺言執行者の報酬付与の申立てを行う場合もあります。
4.新たな遺言執行者に、弁護士を選任なされる場合は、その弁護士費用がいくらになるのか、事前によくお話しされることをお勧めいたします。事務処理上、当初想定された以外の業務を行ってもらわなければならないこともありますが、弁護士報酬に超過分が発生するときはその都度、弁護士からあなたに報告・相談等を行うよう取り決めしておくことも一つの方法です。

参考条文
民法　
第645条　受任者は、委任者の請求があるときは、いつでも委任事務の処理の状況を報告し、委任が終了した後は、遅滞なくその経過及び結果を報告しなければならない。
第646条　受任者は、委任事務を処理するに当たって受け取った金銭その他の物を委任者に引き渡さなければならない。その収取した果実についても、同様とする。
第1012条第2項　第644条から第647条まで及び第650条の規定は、遺言執行者について準用する。
第1015条　遺言執行者は、相続人の代理人とみなす。
第1017条第1項　遺言執行者が数人ある場合には、その任務の執行は、過半数で決する。ただし、遺言者がその遺言に別段の意思を表示したときは、その意思に従う。
　　　　　　第2項　各遺言執行者は、前項の規定にかかわらず、保存行為をすることができる。
第1018条　家庭裁判所は、相続財産の状況その他の事情によって遺言執行者の報酬を定めることができる。ただし、遺言者がその遺言に報酬を定めたときは、この限りでない。

申立書を提出して1回の期日を経て、おそらく申立後1か月半から2か月くらいで審判がでると思います。

時間は回答要旨に記載したとおりですが、ただ家裁における事件の混み具合によってはもっと時間がかかるかもしれません。
辞任手続きをしない場合には、解任しかありません。
費用ですが、弁護士により様々ですので、どのくらいといえません。また報酬がタイムチャージ制(一時間当たりいくらで、かかった時間の合計で請求される場合)でもない限り、時間の経過が即費用の増加には結びつかないと思います。でも二人目の弁護士に見積書の交付は求めるべきでしょう。ただ、費用面で懸念されるのでしたら、ご自分で解任の申立をしてみてはいかがでしょうか。家裁に相談してみれば、申立書の書き方や必要書類など教えてくれますので。