Sachverhalt:
A.
Y._ stellte am 30. April 2012 Strafantrag gegen ihren ehemaligen Lebensgefährten X._ wegen Hausfriedensbruchs und Diebstahls respektive Sachentziehung. Mit Nichtanhandnahmeverfügung vom 16. August 2012 stellte die Staatsanwaltschaft des Kantons Bern das Verfahren wegen Hausfriedensbruchs ein und kündigte in Ziffer 4 des Dispositivs die Einleitung eines Strafbefehlverfahrens wegen Diebstahls an. Mit Strafbefehl vom 21. August 2012 sprach sie gegen X._ eine bedingte Geldstrafe von Fr. 100.-- sowie eine Verbindungsbusse von Fr. 250.-- aus und auferlegte ihm die Verfahrenskosten.
B.
X._ holte weder die Nichtanhandnahmeverfügung noch den Strafbefehl, die ihm per Gerichtsurkunde zugestellt worden waren, innert Frist bei der Post ab. Die Staatsanwaltschaft verschickte beide Verfügungen nochmals per A-Post. Die Nichtanhandnahmeverfügung gelangte X._ am 31. August 2012 zur Kenntnis. Er erhob am 2. September 2012 gegen Ziffer 4 des Dispositivs Beschwerde beim Obergericht des Kantons Bern, auf welche dieses mit Beschluss vom 13. September 2012 nicht eintrat.
X._ nahm am 21. September 2012 vom Strafbefehl und obergerichtlichen Nichteintretensentscheid Kenntnis. Er erhob gleichentags durch seinen beigezogenen Verteidiger "vorsorglich" Einsprache gegen den Strafbefehl.
C.
Am 4. Oktober 2012 stellte er ein Gesuch um Wiederherstellung der Einsprachefrist, das die Staatsanwaltschaft am 11. Oktober 2012 abwies. Die hiergegen erhobene Beschwerde wies das Obergericht am 3. Januar 2013 unter Auferlegung der Verfahrenskosten ab, soweit es darauf eintrat.
D.
X._ führt Beschwerde in Strafsachen und beantragt, das Urteil des Obergerichts vom 3. Januar 2013 sei aufzuheben, das Gesuch um Wiederherstellung der Rechtsmittelfrist gutzuheissen und diese im Strafbefehl vom 21. August 2012 wiederherzustellen. Eventualiter sei festzustellen, dass die Einsprache rechtzeitig erhoben wurde. Subeventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
E.
Die Staatsanwaltschaft verzichtet auf eine Vernehmlassung. Das Obergericht hat sich nicht vernehmen lassen.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung des Gebots von Treu und Glauben und des Grundsatzes des Anspruchs auf ein faires Verfahren. Die Vorinstanz verfalle in überspitzten Formalismus, wenn sie seine Eingabe gegen die Nichtanhandnahmeverfügung als unbeachtlich einstufe. Er habe nicht mit einem Strafbefehl rechnen müssen, da er erst mit Zugang des angefochtenen obergerichtlichen Entscheids auf den Strafbefehl und dessen (separate) Anfechtung hingewiesen worden sei. Zu diesem Zeitpunkt sei die 10-tägige Einsprachefrist aber bereits abgelaufen gewesen. Es sei offensichtlich, dass er eigentlich Einsprache gegen den Strafbefehl habe erheben wollen. Die Vorinstanz hätte seine Eingabe als gegen den bereits erlassenen Strafbefehl gerichtet umdeuten müssen.
1.2. Die Vorinstanz erwägt, die Einsprache vom 21. September 2012 gegen den Strafbefehl sei aufgrund der Zustellfiktion nach Art. 85 Abs. 4 lit. a StPO verspätet. Gründe zur Wiederherstellung der Frist im Sinne von Art. 94 Abs. 1 StPO lägen nicht vor. Der Beschwerdeführer habe seit seiner polizeilichen Einvernahme vom 14. Mai 2012 gewusst, dass gegen ihn ein Strafverfahren laufe. Er habe der Nichtanhandnahmeverfügung entnehmen können, dass hinsichtlich des Diebstahlvorwurfs ein Strafbefehlsverfahren gegen ihn eingeleitet werde. Aufgrund des laufenden Verfahrens hätte er mit weiteren Zustellungen rechnen und besorgt sein müssen, diese rechtzeitig in Empfang zu nehmen. Deshalb sei unerheblich, ob er geglaubt habe, die Einleitung des Strafbefehlsverfahrens mit seiner Beschwerde im Keim ersticken zu können, und ob er konkret gewusst habe, dass ihm ein Strafbefehl zugestellt werde. Daran ändere auch der im Nichteintretensbeschluss gemachte Hinweis auf die Möglichkeit der Einsprache gegen den Strafbefehl nichts. Der Hinweis sei theoretischer Natur gewesen und das Obergericht habe nicht gewusst, dass der Strafbefehl bereits erlassen wurde. Die auf dem Strafbefehl enthaltene Rechtsmittelbelehrung genüge, um den Beschwerdeführer über seine Weiterzugsmöglichkeiten aufzuklären.
1.3.
1.3.1. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG) prüft es grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
1.3.2. Aus dem Prinzip von Treu und Glauben (Art. 5 Abs. 3 BV, Art. 9 BV und Art. 3 Abs. 2 lit. a StPO) leitet die Rechtsprechung ein Recht auf Vertrauensschutz ab. Daraus ergibt sich, dass den Parteien aus einer unrichtigen Rechtsmittelbelehrung grundsätzlich keine Nachteile erwachsen dürfen, wenn sie sich nach Treu und Glauben auf die fehlerhafte Rechtsmittelbelehrung verlassen durften. Dies gilt nicht für die Partei, welche die Unrichtigkeit erkannte oder bei gebührender Aufmerksamkeit hätte erkennen müssen. Allerdings vermag nur eine grobe prozessuale Unsorgfalt der betroffenen Partei oder ihres Anwalts eine unrichtige Rechtsmittelbelehrung aufzuwiegen (vgl. <ref-ruling> E. 1.2.2.1 S. 376 mit Hinweisen). Dieser Grundsatz gilt nicht nur für das Verfahren vor Bundesgericht (Art. 49 BGG), sondern auch für das kantonale Verfahren (vgl. Art. 3 Abs. 1 lit. a StPO; Urteil 6B_295/2011 vom 26. August 2011 E. 1.3 mit Hinweis).
Ob der Prozesspartei eine als grob zu wertende Unsorgfalt vorzuwerfen ist, beurteilt sich nach den konkreten Umständen und ihren Rechtskenntnissen. Ist sie rechtsunkundig und auch nicht rechtskundig vertreten, darf sie nicht der anwaltlich vertretenen Partei gleichgestellt werden, es sei denn, sie verfüge namentlich aus früheren Verfahren über entsprechende Erfahrungen. Eine Überprüfung der in der Rechtsmittelbelehrung enthaltenen Angaben kann von einer Prozesspartei im Übrigen nur verlangt werden, wenn diese über die Kenntnisse verfügt, die es ihr überhaupt ermöglichen, die massgebende Gesetzesbestimmung ausfindig zu machen und gegebenenfalls auszulegen (vgl. <ref-ruling> E. 8.3.2 S. 53 f; <ref-ruling> E. 1.2.2.2 S. 376 f.; je mit Hinweisen).
1.4.
1.4.1. Die Nichtanhandnahmeverfügung der Staatsanwaltschaft enthält folgende Rechtsmittelbelehrung: "Gegen diese Verfügung kann nach Art. 393 ff. StPO innert 10 Tagen seit Eröffnung schriftlich und begründet Beschwerde bei der Beschwerdekammer des Obergerichts des Kantons Bern, Hochschulstrasse 17, Postfach 7475, 3001 Bern, erhoben werden (Art. 310 Abs. 2 i.V.m. Art. 322 Abs. 2 StPO) ".
1.4.2. Die Rechtsmittelbelehrung ist in dieser Form unzutreffend und missverständlich. Die Ankündigung, es werde wegen des Vorwurfs des Diebstahls das "Strafbefehlsverfahren eingeleitet" (Ziffer 4 des Dispositivs), ist nicht anfechtbar. Der Beschwerdeführer war lediglich hinsichtlich Ziffer 3, mit der ihm die Ausrichtung einer Entschädigung versagt wurde, beschwerdelegitimiert. Beim rechtsunkundigen Beschwerdeführer konnte und durfte der Eindruck entstehen, er könne sämtliche Ziffern der Verfügung anfechten und die bevorstehende "Einleitung des Strafbefehlsverfahrens" (respektive den Abschluss der Untersuchung mittels Strafbefehls) im Falle einer Gutheissung seiner Beschwerde durch die Vorinstanz verhindern. Es konnte nicht erwartet werden, dass er anhand der zitierten Gesetzesartikel (Art. 393 ff. StPO und Art. 310 Abs. 2 StPO) die Rechtsmittelbelehrung auf ihre Richtigkeit überprüfte und erkannte, dass er nur eingeschränkt beschwerdelegitimiert war. Dies hätte juristische Kenntnisse erfordert. Unter den gegebenen Umständen kann ihm nicht vorgeworfen werden, er habe sich grob unsorgfältig verhalten, als er auf die falsche Rechtsmittelbelehrung vertraute. Er durfte davon ausgehen, dass seitens der Staatsanwaltschaft bis zum rechtkräftigen Entscheid der Vorinstanz über die Beschwerde keine weiteren Verfahrenshandlungen erfolgten.
1.4.3. Die vom Beschwerdeführer unmittelbar nach Zugang des Nichteintretensbeschlusses der Vorinstanz durch seinen Verteidiger erhobene Einsprache erfolgte demnach fristgerecht. Der angefochtene Entscheid verletzt Art. 5 Abs. 3 BV, Art. 9 BV und Art. 3 Abs. 2 lit. a StPO. Ob die Voraussetzungen für die Wiederherstellung der Einsprachefrist im Sinne von Art. 94 StPO erfüllt sind, ist somit ohne Bedeutung.
2.
Die Beschwerde ist gutzuheissen und der Beschluss der Vorinstanz vom 3. Januar 2013 aufzuheben. Die Sache ist an die Staatsanwaltschaft zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und Abs. 4 BGG). Der Kanton Bern hat dem Beschwerdeführer eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Beschluss des Obergerichts des Kantons Bern vom 3. Januar 2013 aufgehoben und die Sache an die Staatsanwaltschaft des Kantons Bern zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Strafabteilung, Beschwerdekammer in Strafsachen, schriftlich mitgeteilt.
Lausanne, 27. August 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held