Sachverhalt: A. A._ stand seit 1. April 2003 im Dienst der Bundespolizei. Er wurde nach verschiedenen Verfehlungen, unter anderem wegen Missbrauchs der elektronischen Zeiterfassung, am 21. August 2008 fristlos entlassen. Das Eidgenössische Justiz- und Polizeidepartement (EJPD) hiess am 3. April 2009 eine gegen die fristlose Entlassung gerichtete Beschwerde teilweise gut und hielt fest, dass das Arbeitsverhältnis ordentlich auf den 31. Dezember 2008 aufgelöst war. Am 7. Juli 2009 reichte das Bundesamt für Polizei (Fedpol) beim Untersuchungsrichteramt III Bern-Mittelland Strafanzeige wegen Betrugs ein. Dieses sprach A._ mit Strafmandat vom 20. August 2009 schuldig. Es warf ihm vor, während mindestens 9.5 Stunden von seinem Arbeitsplatz abwesend gewesen zu sein, ohne ausgestempelt zu haben. Gegen das Strafmandat erhob A._ Einspruch. Am 26. Januar 2011 verurteilte das Regionalgericht Bern-Mittelland A._ wegen mehrfachen Betrugs sowie wegen (jeweils mehrfacher) einfacher und grober Verkehrsregelverletzung zu einer bedingten Geldstrafe von 60 Tagessätzen zu Fr. 25.-- bei einer Probezeit von zwei Jahren, zu einer Verbindungsbusse von Fr. 500.-- sowie zu einer Übertretungsbusse von Fr. 1'900.--. Die gegen dieses Urteil gerichtete Berufung wies das Obergericht des Kantons Bern am 20. September 2011 ab. Das Bundesgericht hiess die Beschwerde in Strafsachen von A._ am 28. Februar 2013 gut und wies die Sache zur Einstellung des Verfahrens betreffend Betrugsvorwurf an die Vorinstanz zurück (BGE 139 IV 161). Das Obergericht stellte am 15. Mai 2013 das Verfahren wegen mehrfachen Betrugs ein. Gleichzeitig hielt es die Rechtskraft des Schuldpunkts (mehrfache einfache und grobe Verkehrsregelverletzung) sowie des Freispruchs (einfache Verkehrsregelverletzung) fest. Das Obergericht erkannte auf eine bedingte Geldstrafe von 20 Tagessätzen zu Fr. 25.-- bei einer Probezeit von zwei Jahren, eine Verbindungsbusse von Fr. 250.-- sowie eine Übertretungsbusse von Fr. 1'200.--. Es verpflichtete A._ zur Bezahlung der erstinstanzlichen Verfahrenskosten von Fr. 4'500.-- und richtete ihm für das Verfahren vor dem Regionalgericht Bern-Mittelland keine Parteientschädigung aus. Die Entschädigung für die amtliche Verteidigung setzte es auf Fr. 8'577.60 fest. Für das Berufungsverfahren und das Verfahren nach der Rückweisung auferlegte es ihm die Kosten von Fr. 800.-- (während der Kanton Bern Fr. 2'200.-- tragen musste) und richtete ihm eine Parteientschädigung von Fr. 4'689.35 aus. B. A._ führt Beschwerde in Strafsachen. Er beantragt im Wesentlichen, das Urteil des Obergerichts des Kantons Bern sei aufzuheben, und es seien ihm für das erstinstanzliche Verfahren Kosten im Umfang von höchstens Fr. 400.-- und für die beiden Verfahren vor Obergericht Kosten von höchstens Fr. 300.-- aufzuerlegen. Er sei vollständig zu entschädigen. Insbesondere sei er für das erstinstanzliche Verfahren mit 49.6 Stunden zu Fr. 420.-- respektive für die Zeit ab amtlichem Mandat mit 39 Stunden zu Fr. 420.-- sowie für das Verfahren vor Obergericht mit 26.9 Stunden zu Fr. 420.-- zu entschädigen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. 